Network Percolation & the Giant Component

In the Erdős-Rényi random graph model, N nodes are connected by edges added one at a time, each chosen uniformly at random from all possible pairs. A remarkable phase transition occurs at mean degree ⟨k⟩ = 1 (equivalently, M = N/2 edges): below this threshold all connected components are tiny (O(log N) nodes), but above it a single giant component emerges that spans a finite fraction S of all nodes.

This simulation lets you explore this transition in real time. Watch the node colors change as small clusters merge into the giant component. The right panel shows the theoretical prediction S = 1 − e−⟨k⟩S alongside your current graph state.

The critical point ⟨k⟩ = 1 is marked on the phase diagram. Try adding edges slowly near the threshold to observe the dramatic emergence of the giant component.

Frequently Asked Questions

What is the Erdős-Rényi random graph?

The Erdős-Rényi model G(N,p) creates a random graph by taking N nodes and connecting each possible pair of nodes independently with probability p. An equivalent model G(N,M) places exactly M edges chosen uniformly at random. Both models were introduced by Pál Erdős and Alfréd Rényi in 1959–60 and are the fundamental null model for random networks. The key parameter is the mean degree ⟨k⟩ = (N−1)p ≈ Np for large N, which controls the graph's connectivity.

What is the giant component and when does it appear?

A connected component is a maximal set of nodes reachable from each other by following edges. In an Erdős-Rényi graph with mean degree ⟨k⟩ < 1, all components have size O(log N) — the largest is tiny relative to N. As ⟨k⟩ crosses 1 from below, a giant component suddenly emerges that contains a fraction S > 0 of all N nodes, with S satisfying S = 1 − e−⟨k⟩S. This sharp transition is one of the most celebrated results in combinatorics and probability theory.

What is a phase transition in the context of networks?

A phase transition is a sharp, discontinuous (or nearly discontinuous) change in a system property as a control parameter crosses a critical value. In network percolation, the order parameter is S (the giant component fraction) and the control parameter is ⟨k⟩. Below ⟨k⟩=1: S=0 (disordered phase). Above ⟨k⟩=1: S>0 (ordered phase). Near the critical point ⟨k⟩=1, S grows as S ∝ (⟨k⟩−1)β with critical exponent β=1 — a second-order phase transition analogous to ferromagnetism in physics, with ⟨k⟩ playing the role of temperature.

How does Union-Find work for component detection?

Union-Find (also called Disjoint Set Union) is a data structure that efficiently tracks connected components as edges are added. Each node starts as its own component (find(x) returns x). When an edge (a,b) is added, union(a,b) merges the components containing a and b: the root of the smaller tree is attached to the root of the larger. With path compression and union by rank, both find and union run in nearly O(1) amortized time (O(α(N)) where α is the inverse Ackermann function). This allows tracking N=1000 nodes and millions of edges efficiently.

What is bond percolation and how does it relate to random graphs?

Bond percolation on a lattice asks: if each edge (bond) is independently present with probability p, at what p_c does a spanning path first appear? On an infinite d-dimensional lattice p_c is a non-trivial value between 0 and 1. The Erdős-Rényi random graph is bond percolation on the complete graph K_N (all possible edges), giving p_c = 1/N (or ⟨k⟩_c = 1). The two problems have the same critical exponents and belong to the same universality class as mean-field percolation.

What happens exactly at the critical point ⟨k⟩=1?

At the critical point ⟨k⟩=1 (mean degree exactly 1, number of edges M=N/2), the largest component has size O(N2/3) — much larger than the O(log N) subcritical components but much smaller than the O(N) supercritical giant. The component size distribution follows a power law P(s) ∝ s−3/2 for sizes s up to O(N2/3). This critical window, where the system is scale-free and fluctuations are maximal, is the hallmark of a second-order phase transition.

How does network percolation apply to real-world systems?

Percolation has direct applications to network robustness: if nodes or edges fail randomly (at rate 1−p), at what p_c does the network fragment? Internet routers, power grids, and social networks all exhibit percolation thresholds. Real networks (scale-free networks with hubs) have very different percolation properties from Erdős-Rényi: scale-free networks are extremely robust to random failure (no finite p_c) but vulnerable to targeted hub removal. Epidemics also follow percolation dynamics: R₀=1 corresponds to the giant component threshold.

What is the friendship paradox and does it appear here?

The friendship paradox states that your friends have more friends than you on average. In Erdős-Rényi graphs, each node has roughly the same degree, so the paradox is weak. But in real social networks (with heavy-tailed degree distributions), the paradox is strong: randomly chosen neighbors have much higher mean degree than randomly chosen nodes. This matters for percolation: epidemics spread preferentially through high-degree nodes, and network vaccination strategies exploiting the friendship paradox (vaccinate the friend rather than the person) are more effective than random vaccination.

What is the difference between site and bond percolation?

In bond percolation, edges are randomly present or absent (this simulation). In site percolation, nodes are randomly present or absent, and two present nodes are connected if they were originally adjacent. Both exhibit phase transitions but at different critical thresholds. On a square lattice, bond percolation threshold p_c ≈ 0.5 and site percolation threshold p_c ≈ 0.593. On the complete graph (random graph), bond percolation threshold is ⟨k⟩=1 while site percolation threshold is also effectively ⟨k⟩=1 because removing a node removes all its edges.

Why does the giant component fraction satisfy S=1−e^(−⟨k⟩S)?

This self-consistency equation arises from the tree-like local structure of Erdős-Rényi graphs. A node belongs to the giant component if at least one of its ⟨k⟩ random neighbours also belongs to the giant component (following that edge leads into the giant cluster). The probability that a given neighbour does NOT connect to the giant is (1−S). If all ⟨k⟩ Poisson-distributed neighbours avoid the giant, with probability e−⟨k⟩S by the Poisson pgf, then the node is outside the giant. So S = 1 − e−⟨k⟩S is the fixed-point equation for the giant component fraction.

About this simulation

This simulation builds an Erdős-Rényi random graph on N nodes by adding edges one at a time, each drawn uniformly at random from the shuffled list of all possible node pairs. A Union-Find (Disjoint Set Union) structure with path compression and union by rank tracks connected components in near-constant time as edges arrive. A live phase diagram plots the giant component fraction S against mean degree ⟨k⟩ = 2M/N, overlaying your simulation's current state on the theoretical curve S = 1 − e^(−⟨k⟩S). The critical threshold sits exactly at ⟨k⟩ = 1, where the largest component's growth rate abruptly changes character.

🔬 What it shows

N nodes (50–300) connected by randomly chosen edges, added one, ten, or continuously via Play. Each node is coloured by which connected component it belongs to; the largest component (the "giant component" once it forms) is highlighted in blue. A side panel plots S versus ⟨k⟩ against the theoretical curve and marks the critical point ⟨k⟩ = 1 with a dashed line, letting you watch the phase transition happen live.

🎮 How to use

Set the node count N and a target mean degree ⟨k⟩ with the sliders — moving ⟨k⟩ up adds edges immediately, moving it down triggers a full reset. Use Step +1 edge or Add 10 edges for fine control, or press Play to stream edges in continuously at the chosen speed. Watch the Edges M, mean degree ⟨k⟩, giant component fraction S, and component count update live as small clusters merge into one another.

💡 Did you know?

The Erdős-Rényi model, introduced by Pál Erdős and Alfréd Rényi in 1959–60, was one of the first rigorous demonstrations that random structures can undergo a sharp phase transition: below ⟨k⟩ = 1 every component is logarithmically small, but the instant ⟨k⟩ crosses 1, a single component suddenly spans a finite fraction of the entire graph — with no such component existing just below the threshold.

Frequently asked questions

What exactly is being randomised in this simulation?

The simulation pre-shuffles the full list of all possible node pairs (using a Fisher-Yates shuffle) and then reveals them one at a time as edges. This is equivalent to the G(N,M) Erdős-Rényi model, where exactly M edges are chosen uniformly at random from the N(N−1)/2 possible pairs, rather than including each edge independently with probability p — the two formulations converge for large N.

How does the simulation detect the giant component so quickly?

It uses a Union-Find (Disjoint Set Union) data structure. Every node starts in its own component; adding an edge calls union(a,b), which merges the two components by attaching the smaller tree's root to the larger tree's root. With path compression (flattening the tree on find) and union by rank, both operations run in almost constant time, so tracking components for hundreds of nodes and thousands of edges stays fast even in real time.

What does the mean degree ⟨k⟩ slider actually control?

⟨k⟩ is the average number of edges per node, computed as 2M/N where M is the current edge count. The slider sets a target ⟨k⟩; the simulation then computes the target edge count M = round(⟨k⟩·N/2) and either adds edges to reach it (if you increase ⟨k⟩) or performs a full reset and rebuilds from scratch (if you decrease it, since edges can't be un-added incrementally).

Why does the giant component appear so suddenly around ⟨k⟩ = 1?

Below ⟨k⟩ = 1, the random graph is a forest of small tree-like clusters, each of size O(log N), and none of them can grow into a finite fraction of the graph. As ⟨k⟩ crosses 1, the branching process describing cluster growth becomes supercritical: a cluster now has, on average, more than one new node to expand into at each step, so one cluster's growth compounds until it engulfs a fraction S of all N nodes, satisfying S = 1 − e^(−⟨k⟩S). This is a genuine second-order phase transition, not just a smooth trend.

Does the visual layout of nodes affect which nodes end up in the giant component?

No. The on-screen positions are purely cosmetic, generated by a simple force-directed repulsion layout (or a grid layout for large N) purely so nodes don't overlap visually. Which nodes join the giant component is determined entirely by the random edge order and the graph's connectivity — position on screen carries no information about degree or component membership.