Random Graphs: Erdős–Rényi, Phase Transitions & Small-World Networks

Random graph models like Erdős–Rényi reveal phase transitions — sharp thresholds where properties like connectivity appear suddenly — and provide baselines for real-world network analysis. The mathematics of these thresholds, through first and second moment methods, is the same toolkit used in statistical physics and probabilistic combinatorics.

Concepts

Below a critical edge density, a random graph consists of small isolated fragments; above it, a single giant component emerges connecting most vertices. This phase transition — appearing suddenly at an exact threshold — is the foundational fact of random graph theory, and the same mathematical structure governs percolation in physics, satisfiability thresholds in logic, and epidemic spread in epidemiology.

The Erdős–Rényi Model

The Erdős–Rényi model $G(n,p)$ places $n$ vertices and includes each of the $\binom{n}{2}$ possible edges independently with probability $p$. The expected number of edges is $\binom{n}{2}p \approx n^2 p/2$. The degree of any vertex follows $\text{Bin}(n-1, p)$; for $p = c/n$, this converges to a $\text{Poisson}(c)$ distribution as $n \to \infty$.

The closely related model $G(n,m)$ fixes exactly $m$ edges chosen uniformly at random. For $p = m/\binom{n}{2}$, properties of $G(n,m)$ and $G(n,p)$ are asymptotically equivalent for most purposes, so the two models are often used interchangeably.

Phase Transitions and the Giant Component

The most striking feature of $G(n,p)$ is a sharp phase transition at $p = 1/n$ (equivalently $c = 1$ when $p = c/n$):

• For $c < 1$: all connected components have size $O(\log n)$ with high probability (whp).
• At $c = 1$: the largest component has size $\Theta(n^{2/3})$.
• For $c > 1$: a unique giant component of size $\Theta(n)$ exists whp, containing fraction $\beta > 0$ of all vertices where $\beta$ satisfies $\beta = 1 - e^{-c\beta}$.

This phase transition mirrors the percolation transition in statistical physics. The fraction $\beta$ of vertices in the giant component satisfies the self-consistency equation above: a vertex $v$ is in the giant component iff it has at least one neighbor also in the giant component, giving the fixed-point equation via branching process analysis.

The self-consistency equation $\beta = 1 - e^{-c\beta}$ is not just a calculation — it is the survival probability of a Poisson($c$) branching process. Each vertex in the giant component recruits its $\text{Poisson}(c)$ neighbors, and $\beta$ is the probability this process survives to infinity. Branching processes are the right model because $G(n, c/n)$ looks locally like a tree: in any bounded neighborhood, two edge-disjoint paths connecting the same pair of vertices require $O(1/n)$ probability, so cycles are negligible at the local level.

Threshold Functions and Sharp Thresholds

For a monotone graph property $\mathcal{P}$ (one preserved under edge addition), there exists a threshold function $p^*(n)$ such that:

$\Pr[G(n,p) \in \mathcal{P}] \to \begin{cases} 0 & \text{if } p/p^* \to 0 \\ 1 & \text{if } p/p^* \to \infty \end{cases}$

Key thresholds:

• Connectivity: $p^* = \log(n)/n$. At this threshold, the last isolated vertex joins the graph, causing the jump to full connectivity.
• Triangle-freeness: $p^* = n^{-1}$. Below this, expected triangle count is $o(1)$; above it, triangles proliferate.
• Hamiltonicity: $p^* = \log(n)/n$, same as connectivity (the graph becomes Hamiltonian as soon as it has minimum degree $\geq 2$).

The Bollobás–Thomason theorem guarantees every monotone property has a sharp threshold: the transition window has width $o(p^*)$, meaning the jump from probability near 0 to near 1 happens over a negligible range of $p$.

First and Second Moment Methods

First moment (Markov's inequality): If $\mathbb{E}[X] \to 0$ then $\Pr[X \geq 1] \to 0$ (no isolated vertices whp once $p \gg \log n / n$). If $X$ counts objects, then $\Pr[\text{no object exists}] \leq \mathbb{E}[X] \to 0$ if $\mathbb{E}[X] \to \infty$ — but the converse requires more.

Second moment (Paley–Zygmund): To show $\Pr[X > 0] \to 1$, the Cauchy-Schwarz inequality gives:

$\Pr[X > 0] \geq \frac{(\mathbb{E}[X])^2}{\mathbb{E}[X^2]}$

The ratio $\mathbb{E}[X^2]/(\mathbb{E}[X])^2$ is close to 1 when different objects are approximately independent. For isolated vertices at $p = \log n / n$: $\mathbb{E}[X] \to 1$ and the ratio approaches 1, so $\Pr[X > 0] \to 1/2$ — revealing the sharp threshold structure.

Stochastic Block Model

The stochastic block model (SBM) extends $G(n,p)$ with community structure: $n$ vertices are partitioned into $k$ communities of equal size $n/k$. Edges appear with probability $p_{\text{in}}$ within communities and $p_{\text{out}}$ across communities, with $p_{\text{in}} > p_{\text{out}}$.

The Kesten–Stigum threshold determines when community recovery is information-theoretically possible. For 2 equal communities with $p_{\text{in}} = a/n$ and $p_{\text{out}} = b/n$:

$(\sqrt{a} - \sqrt{b})^2 > 2$

Below this threshold, no algorithm (even computationally unbounded) can recover communities better than random guessing. Above it, belief propagation achieves optimal recovery. The SBM is the canonical model for evaluating community detection algorithms, including spectral clustering (which achieves recovery down to the Kesten–Stigum threshold).

Worked Example

First moment method: no isolated vertices above log-threshold. Let $X$ = number of isolated vertices in $G(n,p)$ with $p = c\log(n)/n$, $c > 1$. Each vertex $v$ is isolated with probability $(1-p)^{n-1} \approx e^{-p(n-1)} \approx e^{-c\log n} = n^{-c}$. By linearity:

$\mathbb{E}[X] = n \cdot n^{-c} = n^{1-c} \to 0 \quad (c > 1)$

By Markov's inequality, $\Pr[X \geq 1] \leq \mathbb{E}[X] \to 0$. So whp there are no isolated vertices, which implies (with more work) full connectivity.

Second moment: triangles in $G(n, 1/2)$. Let $X$ = number of triangles. Each triple $\{i,j,k\}$ forms a triangle with probability $(1/2)^3 = 1/8$, giving:

$\mathbb{E}[X] = \binom{n}{3} \cdot \frac{1}{8} \approx \frac{n^3}{48}$

For concentration, compute $\text{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$. Pairs of triangles sharing no edge contribute $(1/8)^2$ each; pairs sharing one edge share 2 edge variables, contributing $(1/8)(1/4)$; pairs sharing two edges (impossible for triangles). The dominant term gives $\text{Var}(X) = \Theta(n^4)$ while $(\mathbb{E}[X])^2 = \Theta(n^6)$. By Chebyshev: $\Pr[|X - \mathbb{E}[X]| > t] \leq \text{Var}(X)/t^2$. Setting $t = \varepsilon \mathbb{E}[X]$ gives $\Pr[|X - \mathbb{E}[X]| > \varepsilon \mathbb{E}[X]] \leq \Theta(n^4)/((\varepsilon n^3)^2) = \Theta(n^{-2}) \to 0$. So $X$ concentrates around its mean.

Connections

Where Your Intuition Breaks

The sharp threshold at $p = 1/n$ makes giant component emergence look like a sudden event — and in the $n \to \infty$ limit it is. For finite $n$, the transition is smooth; there is no $n$ at which a giant component suddenly appears. The threshold is a statement about asymptotic probability, not a finite-$n$ fact. More importantly, the threshold for a giant component ($p = 1/n$) and the threshold for full connectivity ($p = \log n / n$) differ by a factor of $\log n$. Between these thresholds, the graph has a giant component containing most vertices while also having isolated vertices outside it. "Almost all vertices connected" and "the graph is connected" are different events, and the gap between their thresholds is practically significant for any finite network: you can have a well-connected core and isolated outliers simultaneously.