Generalized Scale-Free Models

From Wikipedia, the free encyclopedia

This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message.
This article has been tagged since December 2006.

There has been a burst of activity in the modeling of scale-free complex network. The recipe of Baraba´si and Albert ^[1] has been followed by several variations and generalizations ^[2]^[3]^[4]^[5] and the revamping of previous mathematical works ^[6]. As long as there is power law distribution in a model, it is a scale-free network. The model is a scale-free model.

1 Features
2 Examples
3 See also
4 References

[edit] Features

Image:GSF1.jpg

Fig.[1].Schematic illustration of the evolution of the growing random network. Sites are added sequentially and a single link joins the new site to an earlier site. Adopted from ^[4]

A lot of real networks are scale-free networks. It requires us to build up scale-free models to describe them. There are two ingredients to build up a scale-free model:

1, Adding or removal nodes. Usually we concentrate on adding nodes -- growth.

2, Preferential attachment: The probability $Π$ that new nodes will be connected to the "old" node i.

[edit] Examples

There has been several attempts to generate scale-free network properties. Here are some examples:

Barabasi-Albert model For example, the first scale-free model, Barabasi-Albert model, has a linear preferential attachment $\Pi(k_i)=\frac{k_i}{\sum_j k_j}$ and adding a new node at every time step.

(Note, another general feature of $Π(k)$ in real networks is that $\Pi(0)\neq 0$ , i.e. there is a nonzero probability that a new node attaches to an isolated node. Thus in general $Π(k)$ has the form $Π(k) = A + k α$ , where $A$ is the initial attractiveness of the node.)

[edit] two-levels network model

Dangalchev ^[7] builds a 2-L model by adding a second-order preferential attachment. The attractiveness of a node in the 2-L model depends not only on the number of nodes linked to it but also on the number of links in each of these nodes.

$\Pi(k_i)=\frac{k_i + C \sum_{(i,j)} k_j}{\sum_j k_j + C \sum_j k_j^2}$ , where C is a coefficient between 0 and 1.

[edit] non-linear preferential attachment

The Barabasi-Albert model assumes that the probability $Π(k)$ that a node attaches to node $i$ is proportional to the degree $k$ of node $i$ . This assumption involves two hypotheses: first, that $Π(k)$ depends on $k$ , in contrast to random graphs in which $Π(k) = p$ , and second, that the functional form of $Π(k)$ is linear in $k$ . The precise form of $Π(k)$ is not necessary linear, and recent studies have demonstrated that the degree distribution depends strongly on $Π(k)$

Krapivsky, Redner, and Leyvraz^[4]]] demonstrate that the scale-free nature of the network is destroyed for nonlinear preferential attachment. The only case in which the topology of the network is scale free is that in which the preferential attachment is asymptotically linear, i.e. $\Pi(k_i) \sim a_\infty k_i$ as $k_i \to \infty$ . In this case the rate equation leads to

$P (k)˜ k - γ$ with $\gamma = 1 + \frac{\mu}{a_\infty}$

This way the exponent of the degree distribution can be tuned to any value between 2 and $\infty$ .

[edit] hierarchical network model

There is another kind of scale-free model. They grow according to some patterns. Such as hierarchical network model^[8]]].

The iterative construction leading to a hierarchical network. Starting from a fully connected cluster of five nodes shown in (a) (note that the diagonal nodes are also connected – links not visible), we create four identical replicas, connecting the peripheral nodes of each cluster to the central node of the original cluster, obtaining a network of N = 25 nodes (b). In the next step we create four replicas of the obtained cluster, and connect the peripheral nodes again, as shown in (c), to the central node of the original module, obtaining a N = 125 node network. This process can be continued indefinitely.

[edit] See also

Scale-Free Networks
Barabasi-Albert model
hierarchical network model

[edit] References

^ Barabasi, A.-L. and R. Albert, Science 286, 509(1999).
^ R. Albert, and A.L. Barabasi, Phys. Rev. Lett. 85, 5234(2000).
^ S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.
^ ^a ^b ^c P.L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000).
^ B. Tadic, Physica A 293, 273(2001).
^ S. Bomholdt and H. Ebel, cond-mat/0008465; H.A. Simon, Bimetrika 42, 425(1955).
^ Dangalchev Ch., Phisica A 338, 659 (2004).
^ E. Ravasz and Barabasi Phys. Rev. E 67, 026112 (2003).