Complex Network Percolation

Percolation Theory — Bond & Site Percolation on Networks

In bond percolation, each edge exists independently with probability p. A giant component (spanning cluster proportional to N) appears abruptly at a critical threshold p_c — this is a phase transition of the same universality class as the Ising model.

For Erdős-Rényi graphs G(N, p): p_c = 1/N (giant component at mean degree ⟨k⟩ = 1). For scale-free networks (power-law degree distribution P(k) ~ k^(-γ) with γ ≤ 3): p_c → 0 as N → ∞ — they are extremely robust to random failures but fragile to targeted hub attacks.

Critical exponents: order parameter (giant component fraction) S ~ (p − p_c)^β with β = 5/36 for 2D, β = 1 for mean-field (ER). The percolation threshold equals R₀ = 1 in epidemic spreading (SIR model).