A few hubs, many small nodes — because the rich get richer. Grow a network where each arriving node links preferentially to whoever is already well-connected, and the degree distribution collapses onto a power law P(k) ∝ k−3: no characteristic scale, a hub at every order of magnitude. Down the center, data flows: the seeds go in, the network grows, the heavy tail comes out. The blue team builds and defends it; the red team tries to break it.
source A.-L. Barabási & R. Albert, Emergence of Scaling in Random Networks, Science 286 (1999) 509–512 — doi:10.1126/science.286.5439.509. Rendered, not quoted.
Two ingredients, nothing else:
GROWTH — start from a small connected core; add one node at a time, each bringing m new links. PREFERENTIAL ATTACHMENT — a new node picks each target with probability Π(v) = kv / Σk, proportional to the target's current degree. The well-connected get more connected.
Implemented exactly: every edge drops both endpoints into a pool, so a uniform draw from the pool is a draw ∝ degree — node v occupies exactly kv slots. Live, for the network in the panel:
the-erdos-renyi is democracy: every pair of nodes equally likely, degrees Poisson-bounded around the mean — one scale, no hubs. Keep the growth, swap the rule from coin flip to rich get richer, and the bounded bell becomes an unbounded power law.
Barabási & Albert (1999) named the mechanism that grows the-power-law from a simple local rule. Erdős–Rényi and scale-free are the two poles; each sphere is the other's premise.
Re-grow at a fixed seed and confirm the known truth: γ near 3 with a slope stable across kmin, a hub degree that towers over the mean, links concentrated in the top 1% — and that dropping preference kills all three. If red tampers, this badge goes red.
Four inputs grow the whole network — no data, just a rule:
| seed | meaning |
|---|---|
| N | how many nodes to grow to |
| m | links each new node brings |
| seed | fixes the PRNG — fully reproducible |
| Π ∝ k | the attachment rule (rich-get-richer) |
The core is a tiny connected ring of m+1 nodes; every later node attaches into the pool. That is the entire feed for the engine below.
Preferential: Π(v) ∝ kv. The tail becomes a power law; hubs emerge.
The exponent γ is fitted from the degree CCDF on the spot (γ = 1 − slope), never looked up. Straight line on log–log = power law; a downward bend = exponential.
What the machine produces, proven at seed 1337, N=3000, m=2: a preferential network with fitted γ ≈ 2.81 (the k−3 law, straight on log–log), a hub of degree 122 that grows with N (79 → 122 → 138 for N = 1000 → 3000 → 4000), the top 1% of nodes holding ~12% of all links. Drop preference and it collapses to an exponential blob (kmax ≈ 23).
The blue team's witness (left) confirms these numbers live; the red team (right) tries to make them wrong.
Worse: whether real networks are "scale-free" at all is contested. Broido & Clauset (2019) applied strict statistical tests to ~1000 networks and found strong support for a pure power law in only a minority. "Scale-free" is a useful idealization, not a verified universal law.
"Any BA simulation measures γ = 3 exactly." Cut. γ = 3 is the N → ∞ limit; this finite network fits γ ≈ 2.81. The engine reports the measured value, not the limit.
"Scale-free means fractal / no scale of any kind." Cut. It means no characteristic degree scale — the variance of k diverges — not spatial self-similarity.
"Most real networks are provably scale-free." Kept, corrected. The honest claim is heavy-tailed and power-law-consistent for some; Broido–Clauset 2019 dispute the universal reading.
The red team's move: drop preferential attachment — attach each new node to uniformly random existing nodes. The rich-get-richer rule is gone; degrees become exponential. The blue team's witness (window 7) is watching.
Attach uniformly and the tail collapses: the fitted γ leaves the near-3 band (≈ 4.1), the log–log line bends down, the hub shrinks to ≈ 23. The witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.