Thought Toys · Strategy & computation · Exhibit 45

The rich get richer

Grow a network by adding nodes one at a time. If each newcomer prefers to link to nodes that are already well-connected, a few giant hubs appear out of nothing. Turn that preference off and the very same growth stays a flat, hubless mesh.

The network — node size is its number of links hub0 nodes

Links per node, biggest first (both axes log) each node

—

↳ your turn — drag the preference down to 0% and watch the hubs vanish

What you're seeing

The network is built live, one node at a time. Each new node throws out a fixed number of links (m = 2 here) to nodes already present. The dial sets how it chooses them. At 100% it links in proportion to how many links a node already has — preferential attachment: a node twice as connected is twice as likely to be chosen — so early, lucky nodes pull ahead and keep pulling ahead. A handful balloon into hubs that everything else hangs off, and the rank-degree chart below straightens into a line: a power law, the signature of a scale-free network.

Now drag the dial to 0% and regrow. Every new node now picks its links uniformly at random. Exactly the same number of nodes, the same number of links — but the biggest "hub" is barely above average, the chart bends into a steep exponential drop, and the picture is an even mesh. Nothing about the growth changed except who the newcomers copy. That single choice is the whole difference between a network where popularity compounds and one where it doesn't — the mechanism behind why a few websites, cities, papers, and fortunes end up so far ahead of the pack. It is the same heavy tail as Zipf's law, caught in the act of forming.

The rule, exactly. Start from a small connected seed. Add nodes one at a time; each adds m links, choosing each target with probability P(link to node i) ∝ (1−g)·1 + g·ki where ki is node i's current degree and g is the dial. At g=1 this is the Barabási–Albert model; its degree distribution is a power law P(k) ∝ k−γ with γ = 3. At g=0 it is uniform attachment, whose degree distribution is exponential. Verified in node (improve/verify/45-preferential-attachment.js, on networks of 4,000–8,000 nodes for statistical clarity): at g=1 the tail is a power law (measured exponent ≈ 2.8 on 8,000 nodes — finite-size effects sit just under the asymptotic 3), the complementary distribution is straighter on log-log axes than on semilog, and a genuine hub forms (largest degree ≈ 181 against a mean of 4). Negative control: uniform attachment (g=0) over the identical growth is straighter on semilog axes (an exponential), its largest node reaches only ≈ 22 links — no hub — and its early nodes never become hub-scale. The two runs add the exact same number of edges, so the heavy tail is manufactured entirely by the degree-proportional rule, not by growth alone. (The small live network above shows the trend; the crisp exponent needs the larger node runs.)

Also in Strategy & computation: Aliasing & the Nyquist limit →

All 23 in Strategy & computation
  1. 10The evolution of trust
  2. 23Sorting algorithms
  3. 24PageRank & the random surfer
  4. 25Huffman coding
  5. 26Dijkstra's shortest path
  6. 27Nash equilibria
  7. 33The learning-rate cliff
  8. 36A* pathfinding
  9. 37Braess's paradox
  10. 44Diffie–Hellman key exchange
  11. 45Preferential attachment — you are here
  12. 46Aliasing & the Nyquist limit
  13. 47The secretary problem
  14. 49Freeze too fast, stay stuck
  15. 51Cross one line, and its territory closes
  16. 56Catch one error, miss the next
  17. 57Why more processors stop helping
  18. 58Why a busy line explodes
  19. 59The set that's only sure when it says no
  20. 60The fit that memorizes instead of learns
  21. 61When the wire breaks, pick one
  22. 67Better at both, and still better off trading
  23. 69Everyone was consistent. The vote wasn't.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 45.