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.
This simulation builds an Erdos-Renyi G(n,p) random graph: for every pair of the n nodes, an edge is added independently with probability p. A breadth-first search then partitions the graph into connected components, colouring the largest one red, and a force-directed layout (spring attraction on edges, electrostatic repulsion between all nodes) arranges the graph so its structure becomes visible. A live plot tracks the giant-component fraction against p and marks the theoretical critical threshold p c = 1/(n−1) as a dashed line, so you can watch the phase transition happen in real time rather than just read about it.
As you raise p past the critical threshold pc = 1/(n−1), the many small tree-like components suddenly merge into one giant connected component spanning a macroscopic fraction of all n nodes. The HUD reports the live average degree <k> = (n−1)p, the number of separate components, the giant component's size, and its fraction of the whole graph, while the bottom-left plot traces the measured giant fraction against the theoretical curve S = 1 − exp(−<k>S).
Drag the n slider (20–200) to set the number of nodes and the p slider (0–1) to set the edge probability. Move p slowly across the highlighted threshold to watch isolated clusters snap together into a single red-highlighted giant component. Pause freezes the force-directed layout so you can inspect the current arrangement, and Reset regenerates a fresh random graph with the same n and p.
The giant-component transition is mathematically the same phenomenon as bond percolation on the complete graph, and it shows up far beyond graph theory: an epidemic becomes self-sustaining once its reproduction number R₀ crosses 1, exactly the same threshold condition as <k> crossing 1 here.
It implements the classic Erdos-Renyi G(n,p) model. Given n nodes, every one of the n(n−1)/2 possible edges is included independently with probability p, generated by a single loop that rolls a random number for each pair. There is no preferential attachment or rewiring here — every edge is an independent coin flip, which is what makes the giant-component threshold mathematically clean.
After the edges are generated, the code runs a breadth-first search (BFS) from every unvisited node: it explores all nodes reachable through existing edges layer by layer using a queue, marking each one with a component ID. Repeating this from any remaining unvisited node partitions the whole graph into components in O(n + m) time. The largest resulting component is highlighted in red as the giant component.
The controlling quantity is the average degree <k> = (n−1)·p, shown live in the HUD. Below the critical value <k> = 1 (equivalently p below pc = 1/(n−1)) the graph stays fragmented into small components of size O(log n). Above it, a single giant component emerges whose fraction S of all nodes satisfies the self-consistent equation S = 1 − exp(−<k>S), which the simulation solves numerically and plots alongside the measured data.
It is purely cosmetic, not part of the random graph model itself: every pair of nodes repels like charged particles (an inverse-square repulsion), every edge acts as a spring pulling its two endpoints toward a rest length, and a weak force pulls all nodes toward the canvas centre. Iterating these forces each frame lets connected clusters drift apart from unconnected ones, so the emerging giant component becomes visually obvious rather than just numerically reported.
Not usually. Real networks — social graphs, the web, power grids — tend to have heavy-tailed (power-law) degree distributions, high clustering, and community structure, none of which G(n,p) produces, since every edge here has exactly the same independent probability. More realistic alternatives include the Barabasi-Albert preferential-attachment model and the Watts-Strogatz small-world model, but Erdos-Renyi remains the essential mathematical baseline against which those richer models are compared.