Watts & Strogatz, 1998 — one parameter turns a lattice into a random graph
Before the 1990s there were two standard network models, each holding one extreme. A regular lattice: every node links only to its near neighbours, so "my neighbours are neighbours of each other" is almost always true — high clustering; but crossing from one side to the other takes an enormous number of steps — large average path length. A random graph: edges thrown anywhere, paths startlingly short, but the chance that two of your neighbours happen to be connected is negligible — clustering near zero.
The trouble is that real networks are at neither extreme. Nervous systems, power grids, human social circles, actor collaborations — all of them are clustered and close at once, which is impossible in either standard model.
What Watts and Strogatz asked was: how can those two properties coexist, and how elaborate does the mechanism have to be? Their answer: not elaborate at all. Put a knob between the two extremes and look at the middle.
Note that step 2 only moves edges; it never adds or removes any. So all three frames have exactly the same edge count — every difference that follows comes from the wiring alone.
One common variant is worth knowing: the Newman–Watts version adds a random edge with probability p instead of rewiring. That keeps the graph from fragmenting (rewiring can, with small probability, isolate a stretch), and the qualitative conclusions are identical. Numerical work usually uses this version.
Turn p up slowly from zero and the two curves do not fall together — that is the whole paper.
L collapses fast. At p of one per cent, average path length has already dropped close to random-graph territory. C barely moves. At that same p, more than ninety per cent of the clustering is still there. The wide stretch in between — p spanning two or three orders of magnitude — is the small-world regime.
Why the gap? Because the two things a shortcut does differ enormously in magnitude.
Its benefit to distance is regional. It welds together two stretches of the ring that were far apart, so every pair of nodes that had to travel from one stretch to the other gets a shorter route — whole regions of pairs benefit. Its damage to clustering is pointwise. It destroys one triangle and leaves clustering everywhere else untouched.
A region's worth of gain against one node's worth of loss, so the first few shortcuts are nearly free; once there are enough that paths are already short, adding more buys nothing but destroyed triangles. Returns collapse while costs accumulate linearly — that is the entire reason the middle stretch exists.
Watts and Strogatz checked three real networks: the film-actor collaboration graph, the western US power grid, and the nervous system of C. elegans. All three sit in the middle band — the actor graph's clustering is more than a hundred times that of a size-matched random graph while its path length is about the same.
The model makes one core claim, and it is a useful one: "clustered and close" requires no ingenious mechanism, only a very small number of random cross-circle links.
That claim goes straight to work in several places. Spreading: disease, rumour and fashion can sweep a highly localised population without assuming any special "super-spreading structure" — a few shortcuts suffice. Synchronisation: coupled oscillators (fireflies, cardiac cells, grid frequency) lock together far more readily on small-world topology than on a lattice. Brains: nervous systems must balance dense local processing against global integration while long-range fibres are metabolically expensive, and a small world is the solution under that constraint. Engineering: to shrink a system's diameter, adding a few long links is far cheaper than densifying everywhere.
It also supplies a falsifiable contrast: if a network's clustering is not markedly above that of a size-matched random graph, the small-world account does not apply and you need a different mechanism.