An Erdos-Renyi G(n,p) random graph has n nodes and each of the C(n,2) possible edges is present independently with probability p. As p increases past the critical threshold pc = 1/(n−1), the graph undergoes a dramatic phase transition: a single giant connected component suddenly spans a macroscopic fraction of all nodes.
Average degree: <k> = (n-1) · p
Critical threshold: p_c = 1/(n-1), so <k>_c = 1
Giant component fraction S (self-consistent):
S = 1 - exp(-<k> · S)
Sub-critical (<k> < 1): largest component ~ O(log n)
Super-critical (<k> > 1): largest component ~ S·n
The giant component transition is mathematically identical to bond percolation on the complete graph. The same abrupt connectivity change appears in epidemic spreading (a disease becomes endemic when R0 > 1), the internet's resilience to random failures, and the onset of rigidity in random spring networks.
What is an Erdos-Renyi random graph?
An Erdos-Renyi random graph G(n,p) is a graph on n nodes where each possible edge is included independently with probability p. Introduced in 1959, it is the foundational model for random networks and the starting point for understanding network structure.
What is the giant component phase transition?
When the average degree <k> = (n−1)p crosses the critical value of 1, the largest connected component suddenly grows from O(log n) to O(n) nodes. This abrupt change is a genuine phase transition — the order parameter (giant fraction) changes from 0 to non-zero at a sharp threshold.
What is the critical probability p_c?
The critical probability is p c = 1/(n−1). Below this, the graph consists of many small tree-like components. Above it, a single giant connected component spanning a fraction S of all nodes appears, where S satisfies S = 1 − exp(−<k>S).
Breadth-first search starts from an unvisited node and explores all reachable nodes layer by layer using a queue. All nodes reached in one BFS form one connected component. Repeating for all unvisited nodes partitions the entire graph into its components in O(n + m) time.
Above the threshold, the fraction S satisfies the implicit equation S = 1 − exp(−<k>S). For <k> = 2 (double the threshold), about 80% of nodes join the giant component. As <k> → ∞, S → 1 and essentially all nodes are connected.
By analogy with thermodynamics, the system switches qualitative state at a critical parameter. The giant fraction acts as an order parameter that is zero below pc and non-zero above it, with a singular derivative at the transition — exactly like magnetisation at the Curie point.
Each edge acts like a spring pulling connected nodes together. All node pairs repel each other like charged particles. Iterating these forces brings the graph to a low-energy state where connected clusters group together visually, making component structure immediately apparent.
Right at the critical threshold the largest component has diameter O(n1/3), much larger than the O(log n) diameter of the super-critical regime. This reflects the fragile, tree-like branching structure at the phase transition.
Usually not. Real networks often have power-law degree distributions, high clustering, and community structure — none of which appear in G(n,p). More realistic models include Barabasi-Albert preferential attachment and Watts-Strogatz small worlds. G(n,p) remains the essential mathematical baseline.
Applications include epidemiology (R0 > 1 thresholds), internet resilience to random router failures, social network analysis, LDPC error-correcting codes (sparse random bipartite graphs), and the random 3-SAT satisfiability threshold in computational complexity theory.