Emergence of Scaling in Random Networks

Barabasi and Albert

networks scaling scale-free small-world graph theory structure

@article{barabasi:science-1999,
  title={Emergence of Scaling in Random Networks},
  author={Barab{\'a}si, A.L. and Albert, R.},
  journal={Science},
  volume={286},
  number={5439},
  pages={509--512},
  year={1999}
}

Vertex degree of many real world, large networks follow a scale-free power law distribution

The basic mechanism resulting in this structure has two components:

• New nodes are continuously added to the network
• New nodes prefer to attach to already well connected nodes

Power law vertex degree distribution

• The probability P(k) that a vertex is connected to k other vertices follows $P(k) ~ k^-\lambda$
• Many real world networks may be shown to have a lambda of 2--4

Erdos and Renyi (ER) random graph models do not produce this effect

• Constructed by starting with N vertices and connecting each vertex pair with probability p
• Clustering coefficient is low
• Vertex degree follows a Poisson distribution $P(k) = e^-\lambda * \lambda^k/k!$
  • Lambda is $N * combinations(N-1, k) * p^k * (1-p)^(N-1-k)$

Watts and Strogatz small world graph models also differ

• Constructed from a ring lattice, with each node connected to K/2 neighbors to each side; then, for each edge on one side of each node, with probability \beta remove that edge and connect the node to a different node chosen at random
• Low average path length
• High clustering coefficient
• Probability of finding a vertex of degree k decreases exponentially with k

Two key assumptions common to both models

• Fixed number of nodes
• Uniform probability of connecting or reconnecting to another node

Neither of these holds for many real networks of interest

• Nodes are continually added
• Nodes most likely wind up connected to nodes already well connected
• Taking away either continuous growth or preferential attachment results in a network that does not have a stationary, power law distribution of degree

Construction proceeds as follows:

• Start with m_0 nodes
• At each time step, add a new vertex with m <= m_0 edges
• Probability of connecting to node of degree k is its degree over the sum total degrees in the network ($p(k_i) = k_i / \sum_j k_j$)
• After t time steps, network will have m_0 + t nodes and mt edgese
• \lambda will be 2.9 +/- 0.1
• Power law distribution is independent of time, and therefore system size