Percolation threshold

Why does a randomly wired network stay in fragments and then suddenly become one whole?

Take a thousand dots on a page and start drawing links between randomly chosen pairs. After a hundred links you have a scatter of little islands: pairs, triples, the occasional clump of six. After four hundred you have the same thing, slightly bigger. After five hundred and one, something has changed — roughly half the dots are now in a single connected mass, and the islands that remain are stragglers.

The obvious reading is that the mass grew steadily and you only noticed it late. But that is not what happens, and the difference matters. So let me ask the question that actually separates the two stories: at what moment does adding one more link stop making a slightly bigger clump and start making a whole?

Stop thinking about the network from above and stand on a single dot. Follow one of its links to a neighbour. From that neighbour, how many new dots can you reach — ones you have not already counted? If each dot has on average c links, you arrived along one of them, so you have about c - 1 fresh ones to leave by. Call that the branching number.

Now let the exploration run. Each layer of the search multiplies by roughly that branching number. What happens to a quantity that multiplies by something slightly less than one at every step? It shrinks geometrically and dies. And if it multiplies by something slightly more than one? It does not merely last longer — it has a positive probability of never dying at all. That is the whole transition, and notice that it is a statement about a ratio, not about a total. There is no gradual version of "the branching factor is one".

For the plainest case — the Erdos-Renyi random graph, where every pair of n dots is linked independently — this lands exactly where the argument says. Below a mean degree of one, the largest connected piece is of order log n: tiny, and shrinking in relative terms as the graph grows. Above a mean degree of one, there is a single giant component holding a constant fraction of every dot. The critical point is one link per node on average, and it does not drift with n.

Can we say how big the giant piece is just past the threshold? Let S be the fraction of dots inside it. A dot is outside it only if every one of its links leads to a neighbour who is also outside, which gives the self-consistent condition S = 1 - e^(-cS). At c = 1 the only solution is S = 0; just above, a second solution peels away, growing roughly as 2(c - 1). So the giant component does not appear at full size — it appears at size zero and grows continuously. The suddenness is in the onset, not in a jump.

And here is where the intuition earns its keep, because the threshold is not always 1. On a square lattice, where each site has four fixed neighbours rather than random partners, bond percolation tips at exactly p = 1/2 — proved by Kesten in 1980, though physicists had been confident of it for decades. On a network with a very unequal spread of degrees, the branching argument has to be weighted by how likely you are to arrive at a hub, which gives the Molloy-Reed condition: a giant component exists when the mean of k squared exceeds twice the mean of k. For a scale-free network whose degree exponent sits between 2 and 3, that second moment diverges as the network grows — and the threshold slides toward zero. Such a network is connected at almost any density, which is one reason the internet is so stubbornly hard to fragment by random failure.

Three refinements are worth holding onto.

First, "sudden" describes the birth of the giant component, not a leap in its size. Right at the critical point the largest piece is of order n to the two-thirds — big, but still a vanishing fraction. The sharpness people report is the sharpness of a switch between two regimes, and it only becomes a true discontinuity in the limit of an infinite system. In any finite network the transition is smeared over a window.

Second, the threshold is a property of the rule, not of the picture. Random pairing, a square lattice, and a hub-heavy network are three different rules and they tip at 1, at 1/2, and at nearly zero respectively. Anyone quoting a universal percolation number has left out the structure.

Third — and this is the one that misleads people about robustness — a network that survives random failure superbly can be trivially broken by targeted removal, because deleting the hubs is precisely the operation that collapses the second moment the Molloy-Reed criterion depends on. Same network, same threshold formula, opposite conclusion.

• Explosive percolation, where a mild bias in which links are added sharpens the transition dramatically.
• Bootstrap and k-core percolation, where a node needs several active neighbours rather than one — and the transition turns genuinely discontinuous.
• Epidemic thresholds, where the same branching argument reappears as the basic reproduction number.

Every term the collection defines is gathered in the glossary.