Barabási–Albert model

The distribution of the vertex degrees of a BA graph with 200000 nodes and 2 new edges per step. Plotted in log-log scale. It follows a power law with exponent -2.78.

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}\,}$

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[2]

${\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){\Big |}_{m_{0}=1}=4-\pi \,}$

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}}$.[1]

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

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {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[3]

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {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.

An analytical result for the clustering coefficient of the BA model was obtained by Klemm and Eguíluz[4] and proven by Bollobás.[5] A mean-field approach to study the clustering coefficient was applied by Fronczak, Fronczak and Holyst.[6]

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,

${\displaystyle C(k)=k^{-1}.\,}$

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

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.[8] In [9] (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.

Generalized degree distribution ${\displaystyle F(q,t)}$ of the BA model for ${\displaystyle m=1}$.

The same data is plotted in the self-similar coordinates ${\displaystyle t^{1/2}F(q,N)}$ and ${\displaystyle q/t^{1/2}}$ and it gives an excellent collapsed revealing that ${\displaystyle F(q,t)}$ exhibit dynamic scaling.

By definition, the BA model describes a time developing phenomenon and hence, besides its scale-free property, one could also look for its dynamic scaling property. In the BA network nodes can also be characterized by generalized degree ${\displaystyle q}$, the product of the square root of the birth time of each node and their corresponding degree ${\displaystyle k}$, instead of the degree ${\displaystyle k}$ alone since the time of birth matters in the BA network. We find that the generalized degree distribution ${\displaystyle F(q,t)}$ has some non-trivial features and exhibits dynamic scaling

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

It implies that the distinct plots of ${\displaystyle F(q,t)}$ vs ${\displaystyle q}$ would collapse into a universal curve if we plot ${\displaystyle F(q,t)t^{1/2}}$ vs ${\displaystyle q/t^{1/2}}$.[10]

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

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]