Erdős-Rényi G(n,p) Model

Erdős-Rényi \(G(n,p)\) Model#

The Erdős-Rényi model is the classical model of random graphs. Its simplicity — each edge is present independently with probability \(p\) — belies rich structure: it exhibits sharp phase transitions in connectivity and component size that have driven decades of work in probabilistic combinatorics.

Formal Definition#

Definition (\(G(n,p)\)). The random graph \(G(n,p)\) has vertex set \([n] = \{1, \ldots, n\}\). Each of the \(\binom{n}{2}\) possible edges is included independently with probability \(p \in [0,1]\).

Expected number of edges: $\(\mathbb{E}[|E|] = \binom{n}{2} p \approx \frac{n^2 p}{2}\)$

Degree distribution. Each vertex \(v\) has: $\(\deg(v) \sim \mathrm{Bin}(n-1,\, p)\)$

For large \(n\) with \(\lambda = (n-1)p \approx np\) fixed: $\(P(\deg(v) = k) = \binom{n-1}{k} p^k(1-p)^{n-1-k} \;\xrightarrow{n \to \infty}\; \frac{e^{-\lambda}\lambda^k}{k!}\)$

so degrees converge to a \(\mathrm{Poisson}(\lambda)\) distribution.

Remark. The companion model \(G(n,m)\) fixes exactly \(m\) edges uniformly at random. For \(m = \binom{n}{2}p\) the two models are asymptotically equivalent.

Phase Transitions#

Set \(p = c/n\). Two sharp thresholds govern the large-\(n\) structure of \(G(n,p)\).

Giant Component (Erdős–Rényi 1960)#

Regime

\(c\)

Largest component

Subcritical

\(c < 1\)

\(O(\log n)\) a.s.

Critical

\(c = 1\)

\(\Theta(n^{2/3})\) a.s.

Supercritical

\(c > 1\)

\(\sim \beta n\) a.s.

In the supercritical regime, the giant component fraction \(\beta\) is the unique positive solution to: $\(\beta = 1 - e^{-c\beta}\)$

This fixed-point equation arises from a branching process argument: \(\beta\) is the survival probability of a \(\mathrm{Poisson}(c)\) branching process.

Connectivity Threshold (Erdős–Rényi 1959)#

Write \(p = (\ln n + \omega)/n\). Then:

  • \(\omega \to -\infty\): \(G(n,p)\) has isolated vertices a.s. \(\Rightarrow\) disconnected.

  • \(\omega \to +\infty\): \(G(n,p)\) is connected a.s.

The sharp threshold is \(p^* = \dfrac{\ln n}{n}\).

Intuitively, the last obstacle to connectivity is the last isolated vertex, which disappears exactly at \(p^*\).

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.stats import poisson
from scipy.optimize import brentq

np.random.seed(42)


def gnp_graph(n, p, seed=None):
    """Generate G(n,p): each edge included independently with probability p."""
    rng = np.random.default_rng(seed)
    G = nx.Graph()
    G.add_nodes_from(range(n))
    for i in range(n):
        for j in range(i + 1, n):
            if rng.random() < p:
                G.add_edge(i, j)
    return G

# Visualise the three regimes
n = 200
fig, axes = plt.subplots(1, 3, figsize=(15, 5))

regimes = [
    (0.5 / n, 'Subcritical  c=0.5'),
    (1.0 / n, 'Critical  c=1.0'),
    (3.0 / n, 'Supercritical  c=3.0'),
]

for ax, (p, title) in zip(axes, regimes):
    G = gnp_graph(n, p, seed=42)
    comps = list(nx.connected_components(G))
    largest = max(comps, key=len)
    colors = ['steelblue' if v in largest else 'lightgray' for v in G.nodes()]
    pos = nx.spring_layout(G, seed=42)
    nx.draw_networkx(G, pos=pos, ax=ax, node_size=30, node_color=colors,
                     edge_color='gray', with_labels=False, alpha=0.8)
    ax.set_title(title)
    ax.axis('off')

plt.suptitle('G(n,p) at three regimes  (blue = giant component)', fontsize=13)
plt.tight_layout()
plt.show()

# Degree distribution vs Poisson approximation
n, c = 1000, 3.0
G = gnp_graph(n, c / n, seed=42)
lam = (n - 1) * (c / n)

deg_seq = [d for _, d in G.degree()]
max_k = max(deg_seq)
ks = np.arange(0, max_k + 1)
empirical = np.array([deg_seq.count(k) / n for k in ks])
theoretical = poisson.pmf(ks, lam)

fig, ax = plt.subplots(figsize=(7, 4))
ax.bar(ks, empirical, alpha=0.6, color='steelblue', label='Empirical')
ax.plot(ks, theoretical, 'ro-', markersize=5, label=f'Poisson(lambda={lam:.2f})')
ax.set_xlabel('Degree k')
ax.set_ylabel('P(k)')
ax.set_title(f'Degree distribution: G(n={n}, p=c/n), c={c}')
ax.legend()
plt.tight_layout()
plt.show()

# Giant component fraction vs c = pn
n = 2000
c_vals = np.linspace(0.1, 4.0, 40)
empirical_frac = []

for c in c_vals:
    G = gnp_graph(n, c / n, seed=0)
    largest = max(nx.connected_components(G), key=len)
    empirical_frac.append(len(largest) / n)

# Theory: beta = 1 - exp(-c * beta), unique positive root for c > 1
theory_beta = []
for c in c_vals:
    if c <= 1.0:
        theory_beta.append(0.0)
    else:
        beta = brentq(lambda b: b - 1 + np.exp(-c * b), 1e-9, 1 - 1e-9)
        theory_beta.append(beta)

fig, ax = plt.subplots(figsize=(7, 4))
ax.plot(c_vals, empirical_frac, 'o', color='steelblue', markersize=4, label='Empirical')
ax.plot(c_vals, theory_beta, 'r-', linewidth=2, label='Theory: beta = 1 - exp(-c*beta)')
ax.axvline(1.0, color='gray', linestyle='--', label='c=1 threshold')
ax.set_xlabel('c = pn')
ax.set_ylabel('Fraction in giant component')
ax.set_title('Giant component phase transition in G(n,p)')
ax.legend()
plt.tight_layout()
plt.show()
Contents