Erdős–Rényi Random Graphs: The Giant-Component Phase Transition

The G(n,p) model

The Erdős–Rényi random graph G(n,p) takes n labelled vertices and, for every one of the C(n,2) = n(n−1)/2 possible edges, independently includes it with probability p. Edgar Gilbert introduced this exact formulation in 1959, the same year Paul Erdős and Alfréd Rényi published their closely related G(n,M) model, which instead fixes exactly M edges chosen uniformly at random. The two are asymptotically equivalent when M ≈ p·C(n,2), and G(n,p) is what most people mean today by "an ER graph" because independence between edges makes the mathematics dramatically simpler.

Degree distribution: Poisson, not power-law

Each vertex has n−1 potential neighbours, each included independently with probability p, so a vertex's degree is Binomial(n−1, p). As n grows with np = λ held fixed, this converges to a Poisson distribution:

E[deg(v)] = (n-1)·p ≈ np = λ
P(deg(v) = k) → e^(-λ)·λ^k / k!   (Poisson, n → ∞)

The Poisson tail decays exponentially — vertices far above the mean degree are vanishingly rare. That single fact is the root of the model's most famous limitation, discussed below.

The giant-component phase transition

As the mean degree λ = np crosses 1, the largest connected component undergoes an honest phase transition, in the same sense as water freezing:

λ < 1 (subcritical): largest component O(log n) — scattered fragments
λ = 1 (critical):     largest component Θ(n^(2/3))
λ > 1 (supercritical): a giant component of size f(λ)·n emerges,
                       where f(λ) = 1 - e^(-λ·f(λ))

The window around λ = 1 is extraordinarily narrow — an infinitesimal change in p flips the graph from "no giant component" to "one component swallowing a positive fraction of every vertex." A separate, even sharper threshold governs full connectivity: at p = ln(n)/n, isolated vertices vanish and the whole graph becomes connected with high probability.

Why the model isn't enough on its own

ER graphs do reproduce the "small-world" property — path lengths that grow only as ln(n)/ln(np), matching "six degrees of separation." But real social and biological networks show far more clustering than an ER graph of the same density, and they consistently exhibit power-law degree distributions with a small number of extremely high-degree hubs — a pattern the Poisson-tailed ER model simply cannot produce. This observation, driven home by Barabási and Albert in 1999, motivated preferential-attachment models where new vertices connect preferentially to already-popular ones. ER graphs remain the essential reference point precisely because they show what structure looks like in the complete absence of such mechanisms — the standard null model against which every real network's clustering and degree distribution is compared.

Frequently asked questions

Try it live

Everything above runs in your browser — open Random Graph and watch the giant component snap into existence as average degree crosses 1, a sharp network phase transition happening live.