Erdős–Rényi Phase Transition

In G(n,p), edges appear independently with probability p. At p = 1/n the graph undergoes a sharp phase transition: a giant connected component suddenly emerges containing O(n) nodes. Below the threshold, all components are O(log n).

n (nodes) 80

p·n (= p×n) 1.00

Critical point: p·n = 1.0

Graph statistics Nodes: —
Edges: —
Components: —
Giant size: —
Giant fraction: —

Theory p = —
Expected deg: —
Threshold 1/n: —

If p·n < 1: all components O(log n)
If p·n = 1: largest ~ n^(2/3)
If p·n > 1: giant ~ β·n exists
where β solves β = 1 − e^(−β·p·n)

Erdős–Rényi Giant Component Phase Transition