On the Evolution of Random Graphs
Scatter links at random and, at one precise instant, a giant web snaps into being.
Keep adding random connections to a crowd of strangers and, at one sharp moment, the scattered little groups fuse into a single web that holds almost everyone.
The idea, unpacked
Take a large number of dots and start joining random pairs with lines, one after another. At first you get many tiny, separate clusters. For a long while nothing dramatic happens — the clusters grow only slowly. Then, at a precise tipping point, something sudden occurs: one cluster abruptly outgrows all the others and links up a large fraction of every dot in the whole picture.
Erdős and Rényi found exactly where that tipping point is. The magic number is one connection per dot, on average. Below an average of one link each, the network is a dust of small fragments. Cross that line and a single 'giant' web snaps into being. The change is not gradual; it is a threshold, like water turning to ice at a single temperature.
Where it came from
Paul Erdős — the wandering Hungarian who owned almost nothing, slept on colleagues' sofas, and wrote papers with more co-authors than anyone in history — teamed up with Alfréd Rényi, who liked to say that a mathematician is a machine for turning coffee into theorems. In a burst of papers around 1959–1960 they asked a deceptively simple question: what does a typical graph look like? By imagining the graph growing edge by edge, they discovered that its character changes in sudden jumps, and wrote the first natural history of these random networks.
Why it mattered
Before them, graphs were studied one at a time, by hand. Erdős and Rényi showed you could reason about a whole random ensemble at once and predict its features with near-certainty for large sizes. And their tipping-point idea turned out to be everywhere: the same mathematics describes when a disease tips into an epidemic, when a rumour goes viral, when a power grid or the internet becomes robustly connected, and when a material suddenly starts to conduct. They had found a law of connection itself.
A way to picture it
Think of popcorn kernels scattered across a pan, each able to stick to a neighbour. Sprinkle sticky links at random and you get a few small clumps. Keep going and the clumps stay small — until, at one critical amount of stickiness, the next few links bridge the clumps into a single sheet that spans the whole pan. One moment: loose crumbs. The next: one connected mass. The crossing happens just when each kernel has, on average, a single link.
Where it sits
This is the founding paper of network science. It stands beside percolation theory in physics and epidemic models in biology, which describe the very same sudden tipping point. Later researchers — Watts and Strogatz on 'small worlds', Barabási and Albert on hubs — built richer models, because real networks (friendships, the web, neurons) are not perfectly random. But every one of them measures its network against the Erdős–Rényi random graph: the baseline of pure chance.