Erdős-Rényi Random Graphs, in depth: G(n, p) and G(n, m), the giant component, the connectivity threshold and O(n + m) generation

Two models and their basic statistics

There are two versions. G(n, p) includes each of the C(n, 2) = n(n − 1)/2 possible edges independently with probability p, so the edge count is binomial with mean p·n(n − 1)/2. G(n, m) picks a set of exactly m edges uniformly at random. Erdős and Rényi's 1959–1960 papers studied G(n, m); Gilbert introduced G(n, p) in 1959. For m ≈ p·n(n − 1)/2 they agree on every property that changes monotonically with the edges, such as connectedness or containing a triangle. G(n, p) is easier to analyse, because every edge is independent. G(n, m) is the right choice when you must match a real graph's edge count exactly.

Most interesting behaviour happens when p shrinks as n grows, so results are stated in terms of the mean degree c = p(n − 1). Each vertex's degree is Binomial(n − 1, p), which tends to Poisson(c) for fixed c. Quick facts for G(n, c/n):

The phase transition and the giant component

The headline result (Erdős and Rényi, 1960) is a phase transition at c = 1:

• c < 1: every component has O(log n) vertices. The graph is a dust of small trees.
• c = 1: the largest component has on the order of n^(2/3) vertices. This is the critical window.
• c > 1: one giant component holds a fraction S > 0 of the vertices, and the second largest is O(log n). There is exactly one giant.

S comes from a branching-process argument. Explore outward from a random vertex. In a sparse graph the neighbourhood is locally a tree, and each vertex reached has a Poisson(c) number of new neighbours. Let u be the probability that a vertex is not in the giant, meaning its exploration dies out. That happens exactly when every one of its neighbours' explorations dies out. Averaging over Poisson(c) neighbours gives u = Σₖ e^(−c)cᵏ/k! · uᵏ = e^(−c(1 − u)). Writing S = 1 − u:

S = 1 − exp(−c · S)

S = 0 is always a solution. For c > 1 a second, positive solution appears, and that is the giant's fraction. The slope of the right-hand side at 0 is c, which is why the transition is at exactly c = 1: one expected new neighbour per step is the dividing line between an exploration that dies out and one that keeps growing. Solve it by fixed-point iteration starting from S = 1. It converges quickly away from c = 1 and slowly near it.

The connectivity threshold

A giant is not connectivity. With c a large constant, about n·e^(−c) vertices are still isolated. Connectivity requires every vertex to have degree at least 1. The expected number of isolated vertices is n(1 − p)^(n − 1) ≈ n·e^(−pn), which equals 1 at p = ln n / n. The sharp result: for p = (ln n + x)/n, the probability that G(n, p) is connected tends to exp(−e^(−x)). At that point the last obstacle to connectivity is isolated vertices, and they disappear at the same moment the graph connects.

Thresholds are everywhere in this model, and most properties have their own. For a fixed small subgraph H, the threshold is set by H's densest part: p = n^(−v/e) for the subgraph of H that maximises edges per vertex e/v. A triangle appears around p = 1/n, a 4-clique around n^(−2/3), and in general a k-clique around n^(−2/(k−1)). Hamiltonicity needs minimum degree 2, which arrives at p = (ln n + ln ln n)/n, a little after connectivity. Dense graphs have their own clean results: in G(n, 1/2) the largest clique has about 2·log₂ n vertices. That is why a planted clique of size 3·log₂ n is statistically detectable, yet no polynomial-time algorithm is known that finds planted cliques much smaller than √n, a standard benchmark for average-case hardness.

Finite n converges slowly. For n = 2,000 with 200 samples per point, the measured connected fractions were 0.045, 0.295, 0.775 and 0.865 at x = −1, 0, 1 and 2, against limits of 0.066, 0.368, 0.692 and 0.873. Close, but not equal. So when you design a system around a threshold (a gossip protocol's fan-out, a sensor network's radio range), simulate at the actual n rather than trusting the limit.

Generating large random graphs in O(n + m)

The obvious generator flips a coin for every pair. That is n²/2 random draws, about 5×10⁹ for n = 100,000, even when the graph has only a few hundred thousand edges. Batagelj and Brandes (2005) skip directly to the next included pair instead. The gap between successes in a sequence of Bernoulli(p) trials is geometric, so one uniform draw r gives the skip ⌊log(1 − r)/log(1 − p)⌋. Walking the lower triangle (v, w) with w < v in order makes the whole generator O(n + m):

import math, random

def gnp_edges(n, p, rng=random):
    # Batagelj-Brandes geometric skipping: O(n + m) expected for G(n, p).
    if p <= 0:
        return []
    if p >= 1:
        return [(v, w) for v in range(n) for w in range(v)]
    edges, lp = [], math.log1p(-p)   # accurate even for tiny p
    v, w = 1, -1
    while v < n:
        w += 1 + int(math.log(1.0 - rng.random()) / lp)
        while w >= v and v < n:      # carry the overshoot into later rows
            w -= v
            v += 1
        if v < n:
            edges.append((v, w))
    return edges

The guards matter: at p = 1, log(1 − p) is undefined, and at p = 0 the loop would divide by zero. Using 1 − r rather than r keeps the log away from log(0), because random() can return 0.0. Validation: the mean edge count over 2,000 seeded runs was 122.3 against 122.5 expected for (n, p) = (50, 0.1), 198.9 against 199.0 for (200, 0.01), and 40.46 against 40.5 for (10, 0.9). Every edge was distinct with 0 ≤ w < v. For G(n, m), sample m distinct integers from [0, C(n, 2)) and decode each into a pair. Rejection sampling is fine while m is well below C(n, 2)/2; above that, sample the complement. In networkx, fast_gnp_random_graph implements the skipping method for sparse graphs, and gnp_random_graph and gnm_random_graph are the dense and fixed-edge-count versions.

Worked example: the transition at n = 100,000

To check the theory, n = 100,000 vertices were generated at five mean degrees. Components were found with union-find, the same structure the Newman-Ziff method in percolation uses:

Above the threshold the measured fraction is within 0.002 of S, and the runner-up is tiny, which is the uniqueness of the giant. At c = 1 the largest component is 1,220, the same order as n^(2/3) ≈ 2,154. The second largest (595) is not much smaller, and that is what criticality looks like: no single winner yet. Generation is cheap: one call of gnp_edges took 0.03 s at c = 1 (50,206 edges) and 0.09 s at c = 4 (200,073 edges) in CPython 3.13.

Erdős-Rényi as a null model

The most common practical use is as a null model. Is a network's clustering surprising, or just what its density predicts? Compare it with G(n, m) at the same n and m. Is a motif, such as feed-forward loops in a gene network, over-represented? Count it in a few hundred random graphs and report a z-score. Is a community partition meaningful? Modularity uses a degree-preserving null model rather than ER, and the reason matters. ER does not preserve degrees, so against an ER baseline anything with hubs looks significant. The usual hierarchy:

ER is still the right model where edges really are independent coin flips: random peer selection in gossip and overlay protocols, random key predistribution in sensor networks, and random sparse matrices in benchmarks. It is also the base case for epidemics on networks, where the epidemic threshold reduces to the same branching argument.

Failure modes

• Using ER as the null for a heavy-tailed network. Every statistic correlated with degree then looks significant. Use the configuration model.
• Quadratic generation. The coin-flip loop is fine to n ≈ 10⁴ and hopeless at 10⁶. Use geometric skipping.
• Floating-point p. For tiny p, log(1 - p) loses precision, because 1 − p rounds; math.log1p(-p), as in the generator above, does not.
• Trusting limits at small n. The connectivity numbers above were off by up to 0.08 at n = 2,000. Simulate at your own n.
• Unseeded experiments. Pass an explicit RNG and record its seed, or nobody can reproduce a significance result. Average over many graphs rather than reporting one.
• Mixing up the two parameterisations. c = p(n − 1) is not pn² and is not the edge count. An off-by-one-factor of two between C(n, 2) and n² is the classic bug.

Trade-offs

ER buys analytical clarity and speed: every quantity in this article has a closed form, and the generator is linear. It gives up every structural feature real networks have, including skewed degrees, clustering, communities and spatial embedding. Use it to learn where thresholds come from, to test whether density alone explains a property, and to drive protocols whose links really are random. When the goal is realistic structure, choose a model that builds in the property you care about, and state which properties it keeps.

What to do next

1. Implement gnp_edges and check its mean edge count against p·n(n − 1)/2 for a few (n, p) pairs.
2. Sweep c from 0 to 4 at n = 10⁵, plot the largest-component fraction, and overlay the fixed-point solution of S = 1 − exp(−cS).
3. Measure the connected fraction at p = (ln n + x)/n for your own n, and compare it with exp(−e^(−x)).
4. Take a real network you work with, compute its clustering and degree variance, and compare both with G(n, m) and a configuration model at the same size.
5. Report any significance claim as a z-score over at least a few hundred seeded random graphs, with the null model named.
6. Continue with percolation for the lattice view of the same transition, then epidemics on networks for the dynamic one.