BA model

From Wikipedia, the free encyclopedia

You have new messages (last change).

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

Many real networks exhibit a scale-free degree distribution, but early models of network structure, such as the Erdos-Renyi model (ER) and the Watts and Strogatz model (WS) do not exhibit scale-free structure. The Barabási-Albert (BA) model is a simple algorithm which produces such a scale-free structure.

Contents

[edit] Description

The Barabási-Albert (BA) model incorporates two general concepts in its generation, growth and preferential attachment. Both growth and preferential attachment exist widely in real networks.

[edit] Growth

The total number of nodes in the network increases over time as new nodes are added.

[edit] Preferential attachment

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.

[edit] Definition

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. Now nodes are added to this network one at a time. Each new node is connected to m pre-existing nodes and the probability of connecting to the ith node is given by [1]

\Pi\left(k_i\right)=\frac{k_i}{\sum_jk_j}.

[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}
The degree distribution of the BA Model, which follows a power law.
The degree distribution of the BA Model, which follows a power law[2].
The average path length of the BA Model compared to that of a random graph as a function of network size. The fit on the BA Model data is logarithmic.
The average path length of the BA Model compared to that of a random graph as a function of network size. The fit on the BA Model data is logarithmic[1].

[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

The BA Model is more clustered than a random graph, and the clustering decreases more slowly with network size than for the random graph.
The BA Model is more clustered than a random graph, and the clustering decreases more slowly with network size than for the random graph[1].

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.

[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.

Rescaled spectral density of BA networks, which has a different shape from the semicircular spectral density of random graph.
Rescaled spectral density of BA networks, which has a different shape from the semicircular spectral density of random graph[1].

[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 preferential attachment 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 degree distribution for Model A is an exponential distribution
The degree distribution for Model A is an exponential distribution[1]
The degree distribution for Model B becomes a Gaussian around its mean value
The degree distribution for Model B becomes a Gaussian around its mean value[1]

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] References

  1. ^ a b c d e f g h i | Barabási, A.-L., and R. Albert, Statistical mechanics of complex networks, Reviews of Modern Physics, Vol 74, page 47-97, 2002.
  2. ^ Albert, and Barabási, A.-L., Emergence of Scaling in Random Networks, Science, Vol 286, page 509-512,1999.
Retrieved from "http://en.wikipedia.org../../../b/a/_/BA_model_8926.html"