Barabási–Albert, 1999 — the network version of "rich get richer"; earlier forms in Yule (1925), Simon (1955), Price (1976)
Cited from: Topic 22 · Scale-free networks and preferential attachment
01The Question It Poses
Before the 1990s the default model in network research was the random graph: connect pairs of nodes at random. It makes a clear prediction — the number of edges a node holds (its degree) should have a typical value, with almost every node near the mean and the largest only a few times bigger.
Look up from the model and reality is nothing like that: a few web pages are linked by millions, a few airports carry hundreds of routes, a few papers take most of the citations. These nodes are not slightly larger; they are larger by orders of magnitude.
So the question becomes concrete: what must be added to random wiring for giants to grow by themselves — and how little can you get away with adding? The less you add, the more systems the conclusion covers. This model's answer: two rules suffice.
02The Rules
Start from a small set of already-connected nodes (a handful, wired however you like — the final result does not depend on it).
At each step add one new node, which brings m edges (m is a small fixed number, say 2).
Who does it attach to? The probability of picking a given existing node = that node's current degree ÷ the sum of all degrees in the network. This rule is preferential attachment.
Once attached, move to the next step and add another node. The network keeps growing this way.
Existing edges are never deleted or rewired; existing nodes never leave.
Rule 3 is the whole trick: it never says the newcomer likes anyone, only that the probability is proportional to how many edges the target already holds. Rule 5 is the strongest assumption, and the first one reality breaks.
Draw the choice as a strip divided in proportion to degree: whoever occupies more of the strip is likelier to be hit by a random point. "Preferential" here is a bias in probability, not anyone's preference.
03What You See When It Runs
The degree distribution that comes out is a power law: the number of nodes holding k edges is proportional to k to the minus three. That exponent is derived from the rules — it does not depend on m, nor on how the initial handful was wired.
The figure below is a real run: 30,000 nodes on each side, 2 edges per new node, the only difference being how targets are chosen. Under uniform choice the maximum degree is 27. Under preferential choice it is 616. And the mean degree is identical on both sides — exactly 4.0.
The vertical axis is the fraction of nodes with degree at least k, both axes logarithmic. In these coordinates a power law is a straight line, while uniform choice falls off a cliff — it has a typical value; the straight line does not.
You can also solve for a single node's growth curve: the i-th node to arrive holds, once the network has grown to t nodes, a degree of kᵢ(t) = m·√(t/tᵢ). All nodes are identical in the model; arrival order is the only difference, and time amplifies it as a square root. Early nodes stay ahead, and late ones never catch up.
One last thing that gets skipped: both rules are needed. Keep growth but choose uniformly and you get an exponential distribution with no hubs. Keep preferential attachment on a fixed node set and the distribution never settles — edges pile up until everything is connected to everything. What does the work is the combination: a growing system allocating its increments in proportion to stock.
04What It Explains
It explains one thing: why systems that keep growing, and whose newcomers choose by visibility, end up with heavy-tailed rather than bell-shaped size distributions — web links, citations, air routes, package dependencies, protein interactions all share this structure.
It yields three expectations that data can refute: (1) the degree distribution is heavy-tailed; (2) the rate at which new edges land on a node rises linearly with that node's degree; (3) nodes that arrived early are systematically larger. Expectation (2) is the most useful because it can be measured directly — Jeong, Néda and Barabási did exactly that in 2003, finding citations and the internet close to linear while actor collaboration and scientific co-authorship came out sublinear.
It also displaces a popular bad explanation. When one node is enormous, the default account is "because it is better"; this model shows that in a system obeying the two rules, a crop of giants appears even when every node is identical — so being large is not by itself evidence of being good. As for whether a small early lead really compounds, van de Rijt and colleagues ran randomised field experiments in 2014 on Kickstarter, Wikipedia and others: a randomly conferred initial success did raise later success rates, with diminishing returns.
What It Cannot Explain
It cannot say which node becomes a hub. It predicts that hubs will exist, but with identical nodes the identity of the hub is settled entirely by the first few random choices. On predicting who, the model is explicitly silent.
It cannot explain latecomers overtaking. Under kᵢ(t) = m·√(t/tᵢ) a late node never catches up, yet Google and others plainly did. That needs the Bianconi–Barabási fitness extension, where new edges are allocated by fitness × degree so a young but fit node can overtake. Pure preferential attachment systematically overstates first-mover advantage.
It cannot produce clustering or communities. In the networks it generates, the probability that two of your neighbours know each other approaches zero, and there is no community structure at all. Real networks have both. Any question that turns on clustering or communities is the wrong question to ask this model, however well its degree distribution fits.
It cannot tolerate nonlinearity. Krapivsky, Redner and Leyvraz worked it out in 2000: make the probability proportional to degree raised to the power α and only α = 1 yields a power law. Slightly below 1 the hubs flatten into a stretched exponential; above 1 the links collapse onto a few nodes, and further up onto essentially one. It is a knife-edge condition, not an approximation that is fine if roughly right.
It cannot be used where nodes die and edges rewire. Rule 5 requires that nodes never leave and edges never change. Companies fold, friendships end, dependencies get replaced — such systems need variants with deletion, and the conclusions change with them.
It cannot prove that a given network is scale-free. The model produces power laws, but that does not make it the mechanism behind any particular tail: duplication–divergence, random proportional growth, even plain sampling bias produce the same shape. And when Broido and Clauset ran one consistent test over 927 real networks in 2019, only 4% showed the strongest level of evidence.