Scale-free networks

Created by Claude Opus 5.5, based on the lecture slides by Sang Hoon Lee.

Two networks with the same number of nodes and the same average degree. One is wired at random; the other grows by preferential attachment. Look for the hubs.

Random network

Erdős–Rényi: every link goes between two nodes chosen uniformly at random. Degrees follow a Poisson distribution.

Scale-free network

Barabási–Albert: each new node links to existing nodes with probability proportional to their degree. Degrees follow a power law.

Dot size grows with degree. Hub: at least 3 × ⟨k⟩ links Hover or tap a node to see its neighbors.

Poisson vs power law

The same comparison with many more nodes. On linear axes the power law is a steep L with a long tail. On log–log axes it becomes a straight line, because taking logs of P(k) = c k−γ gives log P(k) = log c − γ log k: a line with slope −γ, the degree exponent.

Average degree follows the slider above

Linear axes

Log–log axes

Random network Poisson with the same ⟨k⟩ Scale-free network Fitted power law

What “scale-free” means

Compare the number of nodes with bk links to the number with k links. For a power law the ratio is always b−γ, whatever k you start from: it depends only on how many times larger you look. No degree is special, so there is no characteristic scale. For a Poisson distribution the ratio depends heavily on k and collapses once k passes ⟨k⟩.

Power law P(k) ∝ k−γ Poisson, ⟨k⟩ = 10 Your starting k

The same exponent decides which averages exist. With a power-law tail, the n-th moment ⟨kn⟩ ∝ ∫ kn−γ dk diverges when γ ≤ n + 1. Most real networks have 2 < γ < 3: a finite mean, but an infinite variance.

No typical degree

For a random network, a node you pick at random has roughly k = ⟨k⟩ ± √⟨k⟩, so ⟨k⟩ is a fair summary. For a scale-free network with γ < 3, ⟨k⟩ stays fixed as the network grows but the spread σk keeps growing, and so does the largest hub. Knowing ⟨k⟩ tells you little about the node you will pick.

Spread σk as N grows

Largest hub as N grows

Random network Scale-free network √⟨k⟩ (left) and √N growth (right)

Why it matters in practice

Robust to accidents, fragile to attacks

Remove nodes and ask what share of the surviving nodes can still reach each other. A random network falls apart once about 1 − 1/⟨k⟩ of its nodes fail. A scale-free network holds on longer and fades out gradually instead of collapsing at a sharp threshold, because almost every node a random failure hits is small. In the limit of very large networks it never breaks apart at all. Remove the hubs first, though, and it shatters faster than the random network.

Random, failures Random, hub attack Scale-free, failures Scale-free, hub attack
10,000 nodes, ⟨k⟩ from the slider at the top

An even smaller world

Hubs act as shortcuts. Paths between two nodes tend to pass through them, so the average distance grows more slowly with network size than in a random network with the same ⟨k⟩.

Random network Scale-free network

Where power laws show up

Heavy-tailed degree distributions appear across very different systems: links between web pages, routers on the internet, protein interactions, email, citations between papers, metabolic reactions. This shared shape is what network scientists call universality. It is also why studying one kind of network often teaches you something about the others.