BA model

From Wikipedia, the free encyclopedia

The Barabási–Albert (BA) model is an algorithm for generating scale-free random graphs. Scale-free networks are very common, and can be found e.g. in social networks, the world-wide web, or networks of proteins reacting with each other in the cell.

Contents

[edit] Concepts

Many real networks have a scale-free degree distribution, but other random graph models such as the Erdős–Rényi model (ER) and the Watts and Strogatz model (WS) do not exhibit scale-free structure. The Barabási–Albert model incorporates two important general concepts: growth and preferential attachment. Both growth and preferential attachment exist widely in real networks.

Growth means that the number of nodes in the network increases over time.

Preferential attachment means that the more connected a node is, the more likely it is to receive new links. Nodes with higher degree have stronger ability to grab links added to the network. Intuitively, the preferential attachment can be understood if we think in terms of social networks connecting people. Here a link from A to B means that person A "knows" or "is acquainted with" person B. Heavily linked nodes represent well-known people with lots of relations. When a newcomer enters the community, s/he is more likely to become acquainted with one of those more visible people rather than with a relative unknown. Similarly, on the web new pages link preferentially to hubs, i.e. very well-known sites such as Google or Wikipedia, rather than to pages that hardly anyone knows. If someone selects a new page to link to by randomly choosing an existing link, the probability of selecting a particular page would be proportional to its degree. This explains the preferential attachment probability rule.

Preferential attachment is an example of a positive feedback cycle where initially random variations (one node initially having more links or having started accumulating links earlier than another) are automatically reinforced, thus greatly magnifying differences. This is also sometimes called the Matthew effect, "the rich get richer", and in chemistry autocatalysis.

[edit] Algorithm

The network begins with an initial network of m0 nodes. It should be noted that m_0\geq 2 and the degree of each node in the initial network should be at least 1, otherwise it will always remain disconnected from the rest of the network.

New nodes are added to the network one at a time. Each new node is connected to m of the existing with a probability that is biased so that it is proportional to the number of links that the existing node already has. Formally, the probability pi that the new node is connected to node i is[1]

p_i = \frac{k_i}{\displaystyle\sum_j k_j},

where ki is the degree of node i. Heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a "preference" to attach themselves to the already heavily linked nodes.

[edit] Properties

[edit] Degree distribution

The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form

P\left(k\right)\sim k^{-3}


[edit] Average path length

The average path length of the BA model increases approximately logarithmically with the size of the network. The actual form has a double logarithmic correction[1] and goes as

l\sim\frac{\ln{N}}{\ln{\ln{N}}}.

The BA model has a systematically shorter average path length than a random graph

[edit] Node degree correlations

Correlations between the degrees of connected nodes develop spontaneously in the BA model because of the way the network evolves. The probability, nkl, of finding a link between nodes of degrees k and l in the BA model is given by

n_{kl}=\frac{4\left(l-1\right)}{k\left(k+1\right)\left(k+l\right)\left(k+l+1\right)\left(k+l+2\right)}+\frac{12\left(l-1\right)}{k\left(k+l-1\right)\left(k+l\right)\left(k+l+1\right)\left(k+l+2\right)}.

This is certainly not the result expected if the distributions were uncorrelated, nkl = k − 3l − 3[1]

[edit] Clustering coefficient

While there is no analytical result for the clustering coefficient of the BA model, the empirically determined clustering coefficients are generally significantly higher for the BA model than for random networks. The clustering coefficient also scales with network size following approximately a power law

C˜N − 0.75.

This behavior is still distinct from the behavior of small world networks where clustering is independent of system size. In the case of hierarchical networks, clustering as a function of node degree also follows a power-law,

C(k) = k − 1.

This result was obtained analytically by Dorogovtsev, Goltsev and Mendes [2].

[edit] Spectral properties

The spectral density of BA model has a different shape from the semicircular spectral density of random graph. It has a triangle-like shape with the top lying well above the semicircle and edges decaying as a power law.


[edit] Limiting cases

[edit] Model A

Model A retains growth but does not include preferential attachment. The probability of a new node connecting to any pre-existing node is equal. The resulting degree distribution in this limit is exponential, indicating that growth alone is not sufficient to produce a scale-free structure.

[edit] Model B

Model B retains preferential attachment but eliminates growth. The model begins with a fixed number of disconnected nodes and adds links, preferentially choosing high degree nodes as link destinations. Though the degree distribution early in the simulation looks scale-free, the distribution is not stable, and it eventually becomes nearly Gaussian as the network nears saturation. So preferential attachment alone is not sufficient to produce a scale-free structure.


The failure of models A and B to lead to a scale-free distribution indicates that growth and preferential attachment are needed simultaneously to reproduce the stationary power-law distribution observed in real networks.[1]

[edit] History

The first proposal for a preferential attachment mechanism to explain power law distributions appears to have been made by Herbert Simon in 1955[3]. It was rediscovered independently by Derek de Solla Price in 1965[4] (and elaborated upon in 1976 [5] using the term "cumulative advantage"), who used it to explain networks of citations between scientific papers. The name "preferential attachment" and the present popularity of scale-free network models is due to the work of Albert-László Barabási and his student Réka Albert analyzing degree distributions on the web in 1999[6].

[edit] References

  1. ^ a b c d Barabási, A.-L., and R. Albert, Statistical mechanics of complex networks, Reviews of Modern Physics, Vol 74, page 47-97, 2002.
  2. ^ S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes, e-print cond-mat/0112143.
  3. ^ Herbert A. Simon (December 1955). "On a Class of Skew Distribution Functions". Biometrika 42 (3-4): 425–440. doi:10.1093/biomet/42.3-4.425. 
  4. ^ D.J. de Solla Price (1965). "Networks of Scientific Papers". Science 149: 510–515. doi:10.1126/science.149.3683.510. 
  5. ^ D.J. de Solla Price (1976). "A general theory of bibliometric and other cumulative advantage processes". Journal of the American Society for Information Science 27: 292–306. doi:10.1002/asi.4630270505. 
  6. ^ Albert-László Barabási & Réka Albert (October 1999). "Emergence of scaling in random networks". Science 286: 509–512. doi:10.1126/science.286.5439.509.