How a giant component appears

1Erdős–Rényi: one self-consistent equation

From the lecture notes: ER_percolation.pdf

In Gilbert’s version of the random graph, \(G_{n,p}\), each of the \(\binom{n}{2}\) pairs is linked independently with probability \(p\). Instead of the giant component itself, track

why the complement? it’s more convenient!

\(u\): the probability that a randomly chosen node does not belong to the giant component.

Node \(i\) stays outside if, for every other node \(j\), either there is no edge (probability \(1-p\)) or there is an edge but \(j\) is itself outside (probability \(pu\)). With \(p=c/(n-1)\),

first given by Erdős and Rényi in 1959

Our original interest is the fraction \(S=1-u\) of nodes in the giant component, which obeys

There is no closed form, but the graphical solution says everything: \(y=1-e^{-cS}\) is concave with slope \(c\) at the origin, so it crosses \(y=S\) a second time only when \(c>1\).

2Near the threshold: \(\beta=\gamma=1\)

From the lecture notes: ER_percolation.pdf

Expanding \(S=1-e^{-cS}\) around \(S=0\),

so \(S\propto(p-p_c)^\beta\) with \(\beta=1\).

in agreement with the mean-field universality class of percolation

The susceptibility analogue is the average size of the (non-percolating) component to which a randomly chosen node belongs. For the random graph (Newman, Sec. 11.6),

From below, \(S=0\) and \(\langle s\rangle=(1-c)^{-1}\). From above, \(S\approx\frac{2}{c^2}(c-1)\), so

giving \(\gamma=1\), with the same amplitude on both sides.

Effective exponents, computed from the exact solution

The local slopes \(d\ln S/d\ln(c-1)\) and \(-d\ln\langle s\rangle/d\ln|c-1|\) converge to 1. Compare with percolation in finite dimensions (Christensen & Moloney, Complexity and Criticality, Table 1.2):

3The same universality class as the Bethe lattice

From the lecture notes: ER_percolation.pdf

For bond percolation on a Bethe lattice with coordination number \(z\) (equations as reproduced in the lecture notes from Prof. Young-Sul Cho’s lecture slides), let \(A\) be the probability that a branch is connected to the infinite cluster. Then

and \(P_\infty\propto(p-p_c)\), so \(\beta=1\) again. For \(z=3\) it closes: \(P_\infty=1-\big(\frac{1-p}{p}\big)^3\) for \(p\ge\frac12\).

the same universality class!

The finite-\(n\) Erdős–Rényi equation has exactly the Bethe form under the dictionary below. Plotting against \(c=p(z-1)\), the Bethe curve tends to the Erdős–Rényi \(S(c)\) as \(z\) grows.

A sampled Bethe lattice

A finite Cayley tree with the coordination number \(z\) chosen above, grown out to generation \(D\) (as deep as keeps the drawing readable). Each bond is occupied with probability \(p=c/(z-1)\), and each bond keeps its random draw as you move the sliders. The cluster containing the root is purple.

On a tree, \(P_\infty\) is the probability that the root’s cluster reaches the boundary as \(D\to\infty\). “Estimate \(P_\infty\)” runs that experiment on \(10^4\) trees of depth 50, grown as a branching process, and compares with the depth-50 recursion and the \(D\to\infty\) result.

4The configuration model: a recipe for \(S\)

From the lecture notes: CM_percolation.pdf

Take a locally tree-like configuration model with degree distribution \(p_k\). For node \(i\) of degree \(k\) to be outside the giant component, none of its \(k\) branches may lead to it. The node at the end of each edge is outside with probability \(u\), and nothing distinguishes one branch from another: they are realized independently. So node \(i\) is outside with probability \(u^k\).

the giant component may be out there, just not connected to node i

Averaging over \(p_k\) gives \(1-S=g_0(u)\). The node reached along an edge has \(k\) further edges with the excess degree distribution \(q_k=(k+1)p_{k+1}/\langle k\rangle\), whose generating function is \(g_1\). This gives the recipe:

1. from \(p_k\), calculate \(g_0(u)=\sum_k p_k u^k\);
2. from \(g_0\), calculate \(g_1(u)=g_0'(u)/g_0'(1)\);
3. solve the self-consistency equation \(u=g_1(u)\);
4. obtain \(S=1-g_0(u)\).

A nontrivial root \(u<1\) exists when \(g_1\) crosses the diagonal, i.e. when the slope at \(u=1\) (the average branching) exceeds 1:

for a “walk” to continue, each node needs at least one more edge, on average

Erdős–Rényi revisited. With \(p_k=e^{-c}c^k/k!\), \(g_0(u)=e^{c(u-1)}\), \(g_0'(1)=c\), so \(g_1(u)=g_0(u)\): the excess degree distribution equals the degree distribution, \(q_k=\frac1c(k+1)e^{-c}\frac{c^{k+1}}{(k+1)!}=p_k\). Then \(u=e^{c(u-1)}\) and \(S=1-e^{-cS}\), as in section 1 (see also S.-W. Son et al., EPL 97, 16006).

A sampled configuration-model network

The theory above assumes \(n\to\infty\). Here is an actual realization for the distribution and parameter you chose: each node draws its degree from \(p_k\) (truncated at \(k=n-1\)), the stubs are paired uniformly at random, and self-loops are discarded. Moving the slider keeps each node’s random draw, so the network changes smoothly. Compare the largest component with \(S\).

5Power-law degrees

From the lecture notes: CM_percolation.pdf

Take the “pure” power law \(p_k=k^{-\gamma}/\zeta(\gamma)\) for \(k\ge1\) and \(p_0=0\), with the Riemann zeta function for normalization. Then

For \(\gamma\le2\), \(\zeta(\gamma-1)\to\infty\), so \(g_1(u)=0\) for every \(u<1\): \(u=0\) is the only solution and \(S=1-g_0(0)=1\). The giant component fills the entire network.

For \(2<\gamma\le3\), \(\langle k\rangle\) is finite while \(\langle k^2\rangle\to\infty\), so \(\langle k^2\rangle-2\langle k\rangle>0\) is always satisfied. Above 3 the giant component survives until \(\zeta(\gamma-2)=2\zeta(\gamma-1)\), at \(\gamma_c\approx\) … (solved in your browser).

careful: with k_min = 1, ⟨k⟩ changes with γ, so it’s not quite a “fair” comparison