The baseline random graph. Take n nodes; include each of the possible edges independently with probability p. Sweep p upward and the graph does not connect smoothly — at p = 1/n a giant component is suddenly born. Rendered, not quoted: the curve below is computed live from a fixed-seed ensemble.
source Erdos, P. & Renyi, A. — On Random Graphs I, Publ. Math. Debrecen 6 (1959) 290–297. renyi.hu archive amber no journal DOI — cited by author/title/year.
G(n, p). A graph on n labelled vertices where each of the n(n−1)/2 possible edges is present independently with probability p, absent with 1−p.
• expected degree of a vertex = (n−1)·p
• degree of a vertex ~ Binomial(n−1, p)
• giant component threshold: pc = 1/n
• connectivity threshold: p = ln(n)/n
Below 1/n the graph is a scatter of small pieces (largest ~ O(log n)). Above it, one component of size Θ(n) dominates — the null model every real network is measured against.
The baseline. Watts–Strogatz (1998) and Barabasi–Albert (1999) exist as departures from this null: real networks show high clustering and heavy-tailed degrees that G(n,p) does not. To claim a network is "small-world" or "scale-free" you first show it differs from the Erdos–Renyi graph with the same n and mean degree.
neighbour → the-watts-strogatz (small-world rewiring of a lattice)
Live re-check. Re-measures the ensemble mean degree at the claimed p = 0.1 and compares against (n−1)·p. If window 6 forces the edges, this badge flips red.
n = 150 nodes · ensemble = 30 fixed-seed graphs
seed = 1234567 (mulberry32 PRNG)
sweep p over [0, 0.05], threshold marked at 1/n ≈ 0.00667
Largest-connected-component fraction vs edge probability p, averaged over the fixed-seed ensemble. The dashed line is p = 1/n.
"The transition is smooth — connectivity just rises gradually with p." No. As n→∞ the emergence of the giant component is a genuine phase transition at p = 1/n: an order parameter (giant fraction) that is zero below and positive above. At finite n it is a steep-but-smooth crossover of width ~n−1/3 — which is exactly why the witness tests a robust jump, not a knife-edge float.
"G(n,p) and G(n,m) are the same model."
→ Related but distinct. G(n,m) fixes the edge count m; G(n,p) fixes each edge's probability. They agree asymptotically when m ≈ p·n(n−1)/2. This engine is strictly G(n,p).
"A giant component means the graph is connected."
→ No. At p just above 1/n a giant exists but many isolated vertices remain. Full connectivity needs the higher threshold p = ln(n)/n.
Planted void (disclosed): force every possible edge present — a complete graph — while still reporting p = 0.1. The measured mean degree jumps to n−1 = 149 and contradicts the claimed (n−1)·0.1 = 14.9. Window 7 catches it.