Generalized scale-free model

There has been a burst of activity in the modeling of scale-free complex networks. The recipe of Barabási and AlbertBarabási, A.-L. and R. Albert, Science 286, 509(1999).] has been followed by several variations and generalizationsR. Albert, and A.L. Barabási, Phys. Rev. Lett. 85, 5234(2000).] S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.] P.L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000).] B. Tadic, Physica A 293, 273(2001).] and the revamping of previous mathematicalworks.S. Bomholdt and H. Ebel, cond-mat/0008465; H.A. Simon, Bimetrika 42, 425(1955).] As long as there is a power law distribution in a model, it is a scale-free network, and a model of that network is a scale-free model.

Features

A lot of real networks are scale-free networks, which require us to build up scale-free models to describe them. There are two ingredients needed to build up a scale-free model:

1. Adding or removing nodes. Usually we concentrate on growing the network, ie. adding nodes.

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

Examples

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

The Barabási-Albert model

For example, the first scale-free model, the Barabasi-Albert model, has a linear preferential attachment $Pi(k\_i)=frac\{k\_i\}\{sum\_j\; k\_j\}$and adds one new node at every time step.

(Note, another general feature of $Pi(k)$ in realnetworks is that $Pi(0)\; eq\; 0$, i.e. there is a nonzero probability that anew node attaches to an isolated node. Thus in general $Pi(k)$ has the form$Pi(k)=A\; +k^alpha$,where $A$ is the initial attractiveness of the node.)

Two-level network model

DangalchevDangalchev Ch., Phisica A 338, 659 (2004).] 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.

Non-linear preferential attachment

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

Krapivsky, Redner, and LeyvrazP.L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000).] ] 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\; o\; infty$. In this case the rate equation leads to

: $P(k)\; sim\; k^\{-gamma\}mbox\{\; 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$.

Hierarchical network model

There is another kind of scale-free model, which grows according to some patterns, such as the [hierarchical network model] E. Ravasz and Barabási Phys. Rev. E 67, 026112 (2003).] .

The iterative construction leading to a hierarchicalnetwork. Starting from a fully connected cluster of five nodes, we create four identical replicas connecting the peripheral nodes of each cluster to the central node ofthe original cluster. From this, we get a network of 25 nodes (N = 25).Repeating the same process, we can create four more replicas of the original cluster - the four peripheral nodes of each one connect to the central node of the nodes created in the first step. This gives N = 125, and the process can continue indefinitely.

ee also

*Scale-free network
*Barabasi-Albert model
*hierarchical network model

References