preferential attachment and scale-free networks
/ BAR-ah-bah-shee AL-bert /
Preferential attachment is a generative growth model that explains WHY networks develop heavy-tailed (power-law) degree distributions: new nodes prefer to attach to nodes that are already well connected, so high-degree vertices accumulate even more edges — 'the rich get richer'. Unlike the configuration model or Chung-Lu, which impose a degree distribution by fiat, preferential attachment produces a power law as an emergent consequence of a simple local rule. The question it answers is: through what mechanism could a network organically grow hubs and a scale-free structure?
The canonical Barabasi-Albert model grows a graph one vertex at a time. At each step a new vertex arrives and connects to m existing vertices, choosing each target with probability proportional to its current degree. Because high-degree vertices are more likely to be chosen, they grow faster, and a careful analysis (the model is essentially an urn / Polya process, related to the older Yule and Simon processes) shows the degree distribution converges to a power law P(degree = k) proportional to k^(-3) for large k — the exponent 3 is universal for linear preferential attachment with this rule. The 'scale-free' name means the degree distribution has no characteristic scale: the tail looks the same on every scale, the signature of a power law. Two structural consequences follow: the network has a few enormous hubs (the oldest, most-connected vertices, the 'first-mover advantage'), and the typical distance is ultra-small, of order (log n)/(log log n), because the hubs act as shortcuts. The rigorous theory (Bollobas-Riordan and others) makes the power-law exponent, the maximum degree (which grows like n^(1/2)), and the diameter precise.
Preferential attachment matters because it is the simplest dynamical explanation of the empirically ubiquitous power law, and it ties random graphs to reinforcement processes, urn models, and the theory of records. It is the model most often invoked to explain the structure of the web, citation networks, and protein interactions. The honest caveats are substantial. First, 'scale-free' has been overclaimed: rigorous statistical work (Broido-Clauset) shows that strong power laws are far rarer in real data than the popularity of the model suggests; many networks are only approximately heavy-tailed or fit a log-normal as well. Second, the exponent 3 is special to LINEAR preferential attachment; sublinear attachment (probability proportional to degree^alpha with alpha < 1) gives a stretched-exponential, not a power law, and superlinear attachment (alpha > 1) gives a single vertex connected to almost everything — so the power law is not robust to the precise attachment rule. Third, the model as usually stated produces no clustering and a tree-like local structure unless modified, so like the other tractable models it misses the triangle-richness of real social networks.
Start with a few vertices and add nodes one by one, each linking to m = 2 earlier vertices chosen with probability proportional to current degree. After n steps the degree distribution is whp close to P(degree = k) about 2 m (m+1) / (k(k+1)(k+2)), which decays like k^(-3). The very first vertices, having had the most time to accumulate links, end up as hubs of degree on the order of n^(1/2).
Linear preferential attachment yields a k^(-3) power law and n^(1/2)-sized hubs — but the exponent is fragile to the rule.
'Scale-free' is widely over-claimed: strong power laws are statistically rarer in real data than the model's fame suggests, and the exponent 3 is special to LINEAR attachment (sublinear gives stretched-exponential, superlinear gives a dominant single hub). The basic model also has no clustering.