HOME

TheInfoList



OR:

The Barabási–Albert (BA) model is an algorithm for generating random scale-free
networks Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...
using a
preferential attachment A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who ...
mechanism. Several natural and human-made systems, including the
Internet The Internet (or internet) is the Global network, global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a internetworking, network of networks ...
, the
World Wide Web The World Wide Web (WWW or simply the Web) is an information system that enables Content (media), content sharing over the Internet through user-friendly ways meant to appeal to users beyond Information technology, IT specialists and hobbyis ...
, citation networks, and some
social networks A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of dyadic ties, and other social interactions between actors. The social network perspective provides a set of meth ...
are thought to be approximately scale-free and certainly contain few nodes (called hubs) with unusually high degree as compared to the other nodes of the network. 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 Albert-László Barabási (born March 30, 1967) is a Romanian-born Hungarian-American physicist, renowned for his pioneering discoveries in network science and network medicine. He is a distinguished university professor and Robert Gray Profe ...
and Réka Albert.


Concepts

Many observed networks (at least approximately) fall into the class of
scale-free networks A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction ''P''(''k'') of nodes in the network having ''k'' connections to other nodes goes for large values of ''k'' as : P( ...
, meaning that they have
power-law In statistics, a power law is a functional relationship between two quantities, where a relative change in one quantity results in a relative change in the other quantity proportional to the change raised to a constant exponent: one quantity var ...
(or scale-free) degree distributions, while random graph models such as the Erdős–Rényi (ER) model and the Watts–Strogatz (WS) model do not exhibit power laws. The Barabási–Albert model is one of several proposed models that generate scale-free networks. It incorporates two important general concepts: growth and
preferential attachment A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who ...
. 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 A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who ...
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 A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of dyadic ties, and other social interactions between actors. The social network perspective provides a set of meth ...
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, they are more likely to become acquainted with one of those more visible people rather than with a relative unknown. The BA model was proposed by assuming that in the World Wide Web, new pages link preferentially to hubs, i.e. very well known sites such as
Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...
, 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. 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 Positive feedback (exacerbating feedback, self-reinforcing feedback) is a process that occurs in a feedback loop where the outcome of a process reinforces the inciting process to build momentum. As such, these forces can exacerbate the effects ...
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 Matthew effect, sometimes called the Matthew principle or cumulative advantage, is the tendency of individuals to accrue social or economic success in proportion to their initial level of popularity, friends, and wealth. It is sometimes summar ...
, "the rich get richer". See also
autocatalysis In chemistry, a chemical reaction is said to be autocatalytic if one of the reaction products is also a catalyst for the same reaction. Many forms of autocatalysis are recognized.Steinfeld J.I., Francisco J.S. and Hase W.L. ''Chemical Kinetics and ...
.


Algorithm

The only parameter in the BA model is m, a positive integer. The network initializes with a network of m_0 \geq m nodes. At each step, add one new node, then sample 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 p_i that the new node is connected to node i is : p_i = \frac, where k_i is the degree of node i and the sum is made over all pre-existing nodes 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 In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network. Definition The degr ...

The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form : P(k)\sim k^ \,


Hirsch index distribution

The
h-index The ''h''-index is an author-level metric that measures both the productivity and citation impact of the publications, initially used for an individual scientist or scholar. The ''h''-index correlates with success indicators such as winning t ...
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 : H(k)\sim k^ \, Furthermore, an analytic result for the density of nodes with
h-index The ''h''-index is an author-level metric that measures both the productivity and citation impact of the publications, initially used for an individual scientist or scholar. The ''h''-index correlates with success indicators such as winning t ...
1 can be obtained in the case where m_0=1 : H(1)\Big, _=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, n_, of finding a link that connects a node of degree k to an ancestor node of degree \ell in the BA model for the special case of m=1 (BA tree) is given by : n_=\frac+\frac. This confirms the existence of degree correlations, because if the distributions were uncorrelated, we would get n_=k^\ell^. For general m , the fraction of links who connect a node of degree k to a node of degree \ell is : p(k,\ell)= \frac \left 1-\frac \right. Also, the nearest-neighbor degree distribution p(\ell\mid k) , that is, the degree distribution of the neighbors of a node with degree k , is given by : p(\ell\mid k)= \frac \left 1-\frac \right . In other words, if we select a node with degree k, and then select one of its neighbors randomly, the probability that this randomly selected neighbor will have degree \ell is given by the expression p(\ell, k) above.


Clustering coefficient

The case for m=1 is trivial: networks are trees and the clustering coefficient is equal to zero. An analytical result for the
clustering coefficient In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups ...
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: : \langle C\rangle \sim lnN^/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 C(k) is practically independent of 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.


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 q, the product of the square root of the birth time of each node and their corresponding degree k, instead of the degree k alone since the time of birth matters in the BA network. We find that the generalized degree distribution F(q, t) has some non-trivial features and exhibits dynamic scaling : F(q,t)\sim t^\phi(q/t^). It implies that the distinct plots of F(q,t) vs q would collapse into a universal curve if we plot F(q,t)t^ vs q/t^.


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 : p_i = \frac, where \alpha is a constant positive exponent. If \alpha=1, NLPA reduces to the BA model and is referred to as "linear". If 0<\alpha<1, NLPA is referred to as "sub-linear" and the degree distribution of the network tends to a stretched exponential distribution. If \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 \alpha<1 and \alpha>1, the scale-free property of the network is broken in the limit of infinite system size. However, if \alpha is only slightly larger than 1, NLPA may result in
degree distribution In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network. Definition The degr ...
s 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 Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American scholar whose work influenced the fields of computer science, economics, and cognitive psychology. His primary research interest was decision-making within organi ...
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 Derek John de Solla Price (22 January 1922 – 3 September 1983) was a British physicist, historian of science, and information scientist. He was known for his investigation of the Antikythera mechanism, an ancient Greek planetary computer, and ...
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 Albert-László Barabási (born March 30, 1967) is a Romanian-born Hungarian-American physicist, renowned for his pioneering discoveries in network science and network medicine. He is a distinguished university professor and Robert Gray Profe ...
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.


See also

* Bianconi–Barabási model * Chinese restaurant process *
Complex networks Complex Networks is an American media and entertainment company for youth culture, based in New York City. It was founded as a bi-monthly magazine, ''Complex'', by fashion designer Marc Eckō. Complex Networks reports on popular and emerging ...
* Erdős–Rényi (ER) model * Price's model *
Percolation theory In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
*
Scale-free network A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction ''P''(''k'') of nodes in the network having ''k'' connections to other nodes goes for large values of ''k'' as : P( ...
*
Small-world network A small-world network is a graph characterized by a high clustering coefficient and low distances. In an example of the social network, high clustering implies the high probability that two friends of one person are friends themselves. The l ...
* Watts and Strogatz model


References


External links


"This Man Could Rule the World""A Java Implementation for Barabási–Albert""Generating Barabási–Albert Model Graphs in Code"
{{DEFAULTSORT:Barabasi-Albert Model Social networks Graph algorithms Random graphs