Erdos-Renyi Percolation: the Giant Component Threshold

A graph made of coin flips

Take N isolated nodes and, for every one of the N(N-1)/2 possible pairs, connect them with an edge independently with probability p. That is the whole recipe for the Erdos-Renyi random graph G(N,p), introduced by Paul Erdos and Alfred Renyi in 1959 (with an equivalent uniform-graph model studied by Edgar Gilbert the same year). No node is special, no edge is more likely than any other - and yet, as p crosses a single sharp threshold, the graph's global shape flips from a scattering of small pieces to one dominant blob.

That flip is a phase transition, the same word used for water turning to steam, and it is the reason percolation shows up everywhere from epidemiology to materials science: it is the simplest possible model of how local connections add up to global connectivity.

Counting edges, not nodes

The control parameter that matters is not p on its own but the average degree, c = p(N-1), which is approximately pN for large N - the expected number of edges touching a typical node. Erdos and Renyi proved that the size of the largest connected component undergoes a sudden change right at c = 1, i.e. at p_c = 1/N.

c < 1  (p < 1/N):  every component is small - the largest is O(log N) nodes
c = 1  (p = 1/N):  the critical point - component sizes follow a power law
c > 1  (p > 1/N):  a single giant component emerges, size proportional to N

Below the threshold the graph is a forest of small trees and cycles - no component holds more than a logarithmic sliver of the nodes, and adding more edges just makes more small pieces. Cross c = 1 and a giant component condenses out of the noise almost overnight: its size grows from O(log N) to a positive fraction of the whole graph within a window of p that shrinks as N grows. This is a branching-process argument in disguise - each node you explore from a starting vertex opens on average c new edges, and a branching process with mean offspring c dies out for certain if c is at most 1 but survives with positive probability if c exceeds 1.

What the giant component looks like

Just above threshold the giant component is still fragile: its relative size s satisfies s = 1 - e^(-cs), a transcendental equation that gives s near zero just past c = 1 and s approaching 1 as c grows past 3 or 4. At exactly c = 1, the component size distribution follows a power law with exponent -5/2, the signature of a critical system with no characteristic scale - the same exponent that turns up in other mean-field percolation and branching-process models.

This is also, not coincidentally, the mathematics behind an epidemic's basic reproduction number R0. If each infected person infects R0 others on average, R0 less than 1 means the chain of infection dies out (subcritical), and R0 greater than 1 means a large-scale outbreak is possible (supercritical) - the SIR model on a random contact network reduces almost exactly to bond percolation with p related to the transmission probability.

Random graphs versus real networks

Real social, biological and infrastructure networks are not Erdos-Renyi graphs - they have far more high-degree hubs than a Poisson degree distribution predicts, usually closer to a power law (the Barabasi-Albert preferred-attachment model captures this). That difference has a large practical consequence discovered by Reka Albert, Hawoong Jeong and Albert-Laszlo Barabasi in 2000: scale-free networks are remarkably robust to random node failure - removing random nodes barely dents the giant component, because most nodes are low-degree - but fragile to targeted removal of the highest-degree hubs, which can shatter connectivity with only a small fraction of nodes removed. An Erdos-Renyi graph, by contrast, is equally vulnerable (or equally robust) to random and targeted attack, since every node looks statistically the same.

Simulating it

for i in range(N):
    for j in range(i + 1, N):
        if random() < p:
            add_edge(i, j)
# union-find tracks component sizes in ~O(N alpha(N)) as edges are added
find_largest_component_size()

Track the largest component's size with a union-find structure as edges are added one at a time (rather than recomputing connectivity from scratch after every edge) and you can watch the giant component condense in real time - the canvas above adds edges at a fixed rate and redraws the component sizes, so the moment c crosses 1 shows up as a visible jump rather than a gradual slope.

Frequently asked questions

Try it live

Everything above runs in your browser — open Network Percolation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.