One Connection Each, and the Web Appears

A litter of clumps, then a continent

Here is the whole experiment. Draw a scatter of dots. Pick two of them at random and join them with a line. Do it again, and again, each time choosing a fresh random pair. There is no map underneath: any dot can be joined to any other, near or far. The only thing that grows is the number of lines.

For a long stretch, nothing much happens. Lines land here and there, and the dots they touch form little clumps, a pair, a triangle, a chain of five. Add more and the clumps grow and occasionally two of them fuse, but they stay clumps. The picture is a litter of small islands adrift in empty space.

Then, over a span so narrow you can miss it, the character of the whole thing changes. One clump stops being a clump. It reaches out and absorbs its neighbours, and their neighbours, and in a rush it becomes a single connected web threaded through most of the scatter. The islands have become a continent. Everything not swallowed stays small, a few stray pairs and singletons off to the side. That dominant piece is the giant component, and the surprise is not that it forms but when, and how abruptly.

The tipping point is astonishingly precise. It is not "when there are lots of lines." It is the moment the number of lines reaches an average of one per dot. Below one connection each, you have a litter. Above one connection each, you have a web. The transition sits exactly on the number one, and this drop is about why.

The same jump, off the grid

Regular readers will recognize the shape of this. A recent drop watched a square grid go from a scatter of open cells to a single cluster spanning edge to edge, snapping across all at once at a sharp density near 0.5927. That was percolation, a phase transition assembled out of coin flips. This is its sibling, with the grid thrown away.

Percolation lived on a lattice, where a cell could only connect to the four neighbours touching it. That geometry is exactly what makes its threshold an ugly, formula-resistant number: connections are local, so a cluster has to physically grow across space. A random graph keeps the coin flips and deletes the geography. Any dot can link to any other, so distance means nothing and a component can gather members from anywhere in the scatter at once. Remove the constraint of space and the messy threshold collapses to the cleanest number there is.

This object has a name and a date. The Erdős–Rényi random graph, studied by Paul Erdős and Alfréd Rényi in a run of papers from 1959 to 1960, is precisely this: take n nodes and add edges between random pairs. Their control knob is the average degree, written c, the mean number of edges meeting each node, which for a graph with m edges is simply c = 2m/n (each edge touches two nodes). Erdős and Rényi proved that as n grows large, the graph passes through a sharp transition at c = 1. Below it, every connected piece is tiny, of size proportional to log n. Above it, exactly one giant piece appears, holding a fixed fraction of all the nodes, and all the other pieces stay small. Nothing gradual, nothing in between.

Module 01 is that experiment, live. It is one fixed graph of 140 nodes whose edges were shuffled into a fixed random order, so turning the dial up only ever adds a line and the giant can only grow, never shrink. You watch this single world knit itself together. At half a connection each the largest piece holds under six percent of the nodes, a genuine litter. At one connection each it is up to fourteen percent, stirring. Push just past that, to an average of one and a half, and the largest piece leaps to over half the graph in ice. The leap is the point: a small change in the dial, right around one, buys an enormous change in the largest piece.

One graph is blurry, ten thousand are sharp

A single graph of 140 nodes cannot show a truly sharp transition, because it is small, and in a small graph everything is smeared by luck. The honest way to see the threshold is the same move percolation used: stop looking at one world and average over many.

Module 02 does exactly that. For each value of the average degree, it builds a fresh random graph, measures the largest component as a fraction of the whole, and averages that fraction over many graphs. The result is a clean curve, the order parameter of the transition: it hugs the floor below an average degree of one, then lifts off above it. And the crucial thing is what happens as the graph grows. Plotted for a hundred nodes, then a thousand, then twelve thousand, the lift-off stops being a gentle slope and tightens toward a corner at exactly one. Below the threshold, the fraction is squeezed down toward zero as the graph grows (at an average degree of 0.9, the largest piece falls from fourteen percent of a 120-node graph to five percent at 1,200 nodes to barely one percent at 12,000). The bigger the system, the more the transition looks like a switch rather than a ramp. That sharpening-with-size is the signature of a real phase transition, the same thing that makes water freeze at a temperature rather than over a range.

Laid over the measured curves is a pale dashed line: the theory. And the measured dots sit right on it. At twelve thousand nodes the browser's own measurement matches the predicted fraction to about three parts in a thousand across the whole range above the threshold. Which raises the obvious question, where does that theory curve come from, and why is its threshold the number one?

Why exactly one

The answer is one line of self-consistency, and it is the prettiest part of the story.

Suppose a fraction S of the nodes belongs to the giant component. Now pick any node at random and ask whether it too is in the giant. It is in the giant exactly when at least one of its edges reaches a node that is already in the giant. On average a node has c edges, and each one independently lands on a giant node with probability S, so the chance that a node misses the giant entirely, on all of its edges, is e^(−cS). Therefore the fraction that connects is one minus that:

S = 1 − e^(−cS).

The giant only exists if it is consistent with itself, and that equation is the consistency condition. Module 03 draws it as a picture. Plot the straight line y = x and the curve y = 1 − e^(−cx) on the same axes, and their crossings are the solutions. Both pass through the origin, so S = 0 is always a solution: no giant is always self-consistent (if nobody is in the giant, nobody joins it). The question is whether there is a second crossing, a positive S.

Here the number one falls out. The curve 1 − e^(−cx) leaves the origin with slope exactly c. If c < 1, the curve rises more slowly than the line and, being concave, never catches it again, so the only solution is S = 0 and there is no giant. If c > 1, the curve starts above the line and must bend back to cross it a second time, at a positive S, and that crossing is the giant. Exactly at c = 1 the curve is tangent to the line at the origin, the two regimes meeting at a single point. The entire phase transition is the moment a slope passes one. Drag the dial in module 03 and watch the second crossing peel away from the origin the instant the average degree crosses one.

The equation even has a clean landmark inside it. Set S = 1/2 and solve: you need c = 2·ln 2 ≈ 1.386. So at an average of about 1.386 connections each, the giant holds exactly half of everything. A hair over one connection buys you a giant; a third more buys you half the world.

The number one, everywhere

This is not a fact about dots. The random graph is the barest possible model of "things connected at random," and the threshold at one connection each is why so many spreading processes have a sharp on/off switch.

A rumour passed to a random contact either dies in a few hops or reaches a crowd, and the dividing line is whether each teller, on average, successfully passes it to more than one new person. An epidemic has the same threshold under a famous name: the basic reproduction number R₀, the average number of people each case infects, and an outbreak fizzles below R₀ = 1 and explodes above it. A power grid or a road network holds together as one connected system, or fragments into islands, on the same knife-edge of links per node. In each case the giant component is the difference between a local event and a system-wide one, and in each case the threshold is one.

It is worth sitting with how little it takes. Below the line, a network can be enormous and still be nothing but scattered fragments, the largest of them only log n nodes across, vanishingly small next to the whole. Add edges until each node has, on average, just barely more than one, and a structure the size of the entire system appears out of nowhere. Not a gradual thickening. A snap. Erdős and Rényi found the exact place it happens, and it is the first counting number, sitting right where a slope crosses one.

Everything above ran in your browser, on nothing but a random-number generator and a union-find that merges dots as their edges arrive. No data was fetched. The threshold was not looked up. It was measured, live, and it landed on one.