Barabási–Albert model
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism.
The BA model tries to explain the existence of such nodes in real networks.
The algorithm is named for its inventors Albert-László Barabási and Réka Albert.
It 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 a higher degree have a 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.
Heavily linked nodes represent well-known people with lots of relations.
When a newcomer enters the community, they are more likely to become acquainted with one of those more visible people rather than with a relative unknown.
The BA model claims that this explains the preferential attachment probability rule.
Later, the Bianconi–Barabási model works to address this issue by introducing a "fitness" parameter.
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.
The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form 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] Furthermore, an analytic result for the density of nodes with h-index 1 can be obtained in the case where
Correlations between the degrees of connected nodes develop spontaneously in the BA model because of the way the network evolves.
(BA tree) is given by This confirms the existence of degree correlations, because if the distributions were uncorrelated, we would get
An analytical result for the clustering coefficient of the BA model was obtained by Klemm and Eguíluz[4] and proven by Bollobás.
[6] The average clustering coefficient of the Barabási-Albert model depends on the size of the network N: This behavior is distinct from the behavior of small-world networks where clustering is independent of system size.
It has a triangle-like shape with the top lying well above the semicircle and edges decaying as a power law.
has some non-trivial features and exhibits dynamic scaling It implies that the distinct plots of
The resulting degree distribution in this limit is geometric,[10] indicating that growth 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.
[11] The NLPA algorithm is identical to the BA model with the attachment probability replaced by the more general form where
, the scale-free property of the network is broken in the limit of infinite system size.
, NLPA may result in degree distributions which appear to be transiently scale free.
[12] Preferential attachment made its first appearance in 1923 in the celebrated urn model of the Hungarian mathematician György Pólya in 1923.
[13] The master equation method, which yields a more transparent derivation, was applied to the problem by Herbert A. Simon in 1955[14] 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.
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.
