- 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 formPi(k)=A +k^alpha,where A is the initial attractiveness of the node.)
Two-level network model
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)
: 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
Wikimedia Foundation. 2010.