Six Degrees of Separation & Small-World Networks

A letter, a stranger, and six steps

In 1967 the psychologist Stanley Milgram ran an experiment now legendary in network science: he gave a stack of letters to volunteers in Nebraska and Kansas, addressed to a stockbroker in Boston, with instructions to forward the letter only to someone they knew personally who might be closer, socially, to the target. Chains that completed averaged around five to six intermediaries — the origin of the phrase "six degrees of separation." Most chains never finished at all, so the number is really a property of the successful paths rather than a rigorously proven fact about the whole social graph, but the intuition it captured — that our personal networks, though locally tight-knit, are laced with just enough long-range links to make the whole world surprisingly close — turned out to be right, and it took three more decades before anyone built a model that explained why.

The Watts-Strogatz construction

Duncan Watts and Steven Strogatz supplied that model in 1998. Start with a ring lattice: n nodes arranged in a circle, each connected to its k nearest neighbours on either side. This regular structure has exactly the property real friendship networks have locally — your neighbours' neighbours are often your neighbours too, a high clustering coefficient — but it is a terrible model for the whole network, because getting from one side of the ring to the other takes a number of hops proportional to n, growing linearly with the size of the network.

start:  ring lattice, n nodes, each linked to its k nearest neighbours
        → high clustering C(0), long average path length L(0) ~ n

for each edge, with probability p:
  rewire one endpoint to a uniformly random node

p = 0    → regular lattice   (high C, long L)
p = 1    → random graph      (low C,  short L)
0 < p < 1 (small)  → SMALL WORLD: C stays high, L collapses fast

The construction then rewires each edge independently to a uniformly random node with some small probability p. At p = 0 you have the original slow, clustered lattice; at p = 1 you have an Erdős-Rényi-style random graph, with short paths but almost no clustering. The surprise Watts and Strogatz demonstrated is what happens in between: even a very small p — rewiring just a few percent of edges — is enough to collapse the average path length nearly all the way to its random-graph value, while the clustering coefficient barely drops from its lattice value. There is a wide range of p where the network has both properties simultaneously: locally clustered like the lattice, globally as reachable as the random graph.

live demo · rewiring a ring lattice into a small-world network● LIVE

Why a few shortcuts do so much work

The intuition for the asymmetric collapse is that clustering is a local property — it depends only on whether your immediate neighbours know each other — so a handful of random rewired edges scattered across the whole network affects only a tiny fraction of local neighbourhoods and barely dents the average. Path length, by contrast, is a global property, and a single long-range edge can slash the distance between two otherwise-distant regions of the network from dozens of hops down to two or three. Because these long-range shortcuts also connect to each other, their effect compounds rapidly: a small number of random long edges quickly creates a web of shortcuts between shortcuts, and the average path length across the whole network scales not with n but with log n.

Where the small-world property shows up

Watts and Strogatz's original paper tested the model against the neural network of the nematode C. elegans, the North American power grid, and the collaboration network of film actors — all three showed the signature short-path, high-clustering combination. The same structural fingerprint shows up in social media graphs (Facebook's global network was found to average roughly 3.5 degrees of separation in a 2011 study), and it has direct practical consequences for epidemiology: because a disease can travel across a network as fast as its shortest paths allow, even a small number of long-range social or travel connections can turn what would be a slow, geographically contained outbreak into one that reaches the whole population rapidly.

Frequently asked questions

Did Stanley Milgram actually prove six degrees of separation?

Not quite. His 1967 small-world experiment tracked chains of letters forwarded through personal acquaintances toward a target person, and completed chains averaged around five to six intermediaries — but most chains never arrived at all, so the famous number describes the successful chains, not a proven property of the whole social graph. Later, much larger studies, including a 2011 analysis of Facebook's friendship graph, found comparably short average distances, lending real support to the idea.

How can a network have both short paths and tight-knit clusters?

That combination is exactly what makes a network small-world rather than merely random. Most of the network stays locally clustered — your friends tend to know each other — while a small number of long-range rewired edges act as shortcuts between otherwise distant clusters, collapsing the average path length far more than the clustering coefficient falls.

Why does the average path length drop so fast even at low rewiring probability?

Because a single long-range shortcut can cut the distance between two far-apart clusters from dozens of hops down to just two or three, and that effect compounds — a handful of random long edges creates a web of shortcuts between shortcuts. Watts and Strogatz showed the average path length collapses almost as soon as any rewiring is introduced, while the local clustering coefficient barely moves until the rewiring probability gets much higher.

Try it live

Everything above runs in your browser — open Six Degrees of Separation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Six Degrees of Separation simulation

Six Degrees of Separation: The Watts-Strogatz Small-World Network