Barabási–Albert model

Algorithm

The only parameter in the BA model is ${\displaystyle m}$, a positive integer. The network initializes with a network of ${\displaystyle m_0\ge m}$ nodes.

At each step, add one new node, then sample ${\displaystyle m}$ neighbors among the existing vertices from the network, with a probability that is proportional to the number of links that the existing nodes already have (The original papers did not specify how to handle cases where the same existing node is chosen multiple times.). Formally, the probability ${\displaystyle p_i}$ that the new node is connected to node ${\displaystyle i}$ is

${\displaystyle p_i=\frac{k_i}{\sum _j{k}_j},}$

where ${\displaystyle k_i}$ is the degree of node ${\displaystyle i}$ and the sum is made over all pre-existing nodes ${\displaystyle j}$ (i.e. the denominator results in twice the current number of edges in the network). This step can be performed by first uniformly sampling one edge, then sampling one of the two vertices on the edge.

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.

Properties

Degree distribution

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

${\displaystyle P(k)\sim k^{-3}}$

Hirsch index distribution

The h-index or Hirsch index distribution was shown to also be scale free and was proposed as the lobby index, to be used as a centrality measure

${\displaystyle H(k)\sim k^{-6}}$

Furthermore, an analytic result for the density of nodes with h-index 1 can be obtained in the case where ${\displaystyle m_0=1}$

${\displaystyle H(1){|}_{m_0=1}=4-\pi }$

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, ${\displaystyle n_{k\ell }}$, of finding a link that connects a node of degree ${\displaystyle k}$ to an ancestor node of degree ${\displaystyle \ell }$ in the BA model for the special case of ${\displaystyle m=1}$ (BA tree) is given by

${\displaystyle n_{k\ell }=\frac{4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}+\frac{12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}.}$

This confirms the existence of degree correlations, because if the distributions were uncorrelated, we would get ${\displaystyle n_{k\ell }=k^{-3}{\ell }^{-3}}$.

For general ${\displaystyle m}$, the fraction of links who connect a node of degree ${\displaystyle k}$ to a node of degree ${\displaystyle \ell }$ is

${\displaystyle p(k,\ell )=\frac{2m(m+1)}{k(k+1)\ell (\ell +1)}\left[1-\frac{(\genfrac{}{}{0ex}{}{2m+2}{m+1})(\genfrac{}{}{0ex}{}{k+\ell -2m}{\ell -m})}{(\genfrac{}{}{0ex}{}{k+\ell +2}{\ell +1})}\right].}$

Also, the nearest-neighbor degree distribution ${\displaystyle p(\ell \mid k)}$, that is, the degree distribution of the neighbors of a node with degree ${\displaystyle k}$, is given by

${\displaystyle p(\ell \mid k)=\frac{m(k+2)}{k\ell (\ell +1)}\left[1-\frac{(\genfrac{}{}{0ex}{}{2m+2}{m+1})(\genfrac{}{}{0ex}{}{k+\ell -2m}{\ell -m})}{(\genfrac{}{}{0ex}{}{k+\ell +2}{\ell +1})}\right].}$

In other words, if we select a node with degree ${\displaystyle k}$, and then select one of its neighbors randomly, the probability that this randomly selected neighbor will have degree ${\displaystyle \ell }$ is given by the expression ${\displaystyle p(\ell |k)}$ above.

Clustering coefficient

The case for ${\displaystyle m=1}$ is trivial: networks are trees and the clustering coefficient is equal to zero. An analytical result for the clustering coefficient of the BA model was obtained by Klemm and Eguíluz and proven by Bollobás. A mean-field approach to study the clustering coefficient was applied by Fronczak, Fronczak and Holyst.

The average clustering coefficient of the Barabási–Albert model depends on the size of the network N:

${\displaystyle ⟨C⟩\sim ln{N}^2/N.}$

This behavior is distinct from the behavior of small-world networks where clustering is independent of system size.

The clustering as a function of node degree ${\displaystyle C(k)}$ is practically independent of ${\displaystyle k}$.

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. In (Section 5.1), it was proved that the shape of this spectral density is not an exact triangular function by analyzing the moments of the spectral density as a function of the power-law exponent.

Limiting cases

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 geometric, indicating that growth alone is not sufficient to produce a scale-free structure.

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.

Non-linear preferential attachment

The BA model can be thought of as a specific case of the more general non-linear preferential attachment (NLPA) model. The NLPA algorithm is identical to the BA model with the attachment probability replaced by the more general form

${\displaystyle p_i=\frac{k_i^{\alpha }}{\sum _j{k}_j^{\alpha }},}$

where ${\displaystyle \alpha }$ is a constant positive exponent. If ${\displaystyle \alpha =1}$, NLPA reduces to the BA model and is referred to as "linear". If ${\displaystyle 0<\alpha <1}$, NLPA is referred to as "sub-linear" and the degree distribution of the network tends to a stretched exponential distribution. If ${\displaystyle \alpha >1}$, NLPA is referred to as "super-linear" and a small number of nodes connect to almost all other nodes in the network. For both ${\displaystyle \alpha <1}$ and ${\displaystyle \alpha >1}$, the scale-free property of the network is broken in the limit of infinite system size. However, if ${\displaystyle \alpha }$ is only slightly larger than ${\displaystyle 1}$, NLPA may result in degree distributions which appear to be transiently scale free.

History

Preferential attachment made its first appearance in 1923 in the celebrated urn model of the Hungarian mathematician György Pólya in 1923. The master equation method, which yields a more transparent derivation, was applied to the problem by Herbert A. Simon in 1955 in the course of studies of the sizes of cities and other phenomena. It was first applied to explain citation frequencies by Derek de Solla Price in 1976. Price was interested in the accumulation of citations of scientific papers and the Price model used "cumulative advantage" (his name for preferential attachment) to generate a fat tailed distribution. In the language of modern citations network, Price's model produces a directed network, i.e. the version of the Barabási–Albert model. 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 Réka Albert, who discovered that a similar process is present in real networks, and applied in 1999 preferential attachment to explain the numerically observed degree distributions on the web.