Small-world networks

Why can a message reach a stranger on the far side of the world in only a handful of steps?

Almost everyone you know is someone you could have met: a neighbour, a colleague, a friend of a friend. Your acquaintances overlap heavily with each other. That is a local structure, and local structures ought to make distant things far away — if every step moves you a village over, crossing a continent takes a very large number of steps. And yet the folk claim is that six or so will do it. Both things seem true. How can a network be simultaneously so cliquish and so shallow?

Push on the two extremes first, because the answer lives between them.

Imagine everyone arranged in a huge ring, each person knowing only the ten people nearest them along the circle. This network is intensely clustered: your friends know each other, because they are standing next to each other. But to reach someone on the far side you must walk the ring, and the number of steps grows in proportion to the population. A billion people means millions of steps. Local, and deep.

Now the opposite: everyone's ten acquaintances chosen uniformly at random from the whole population. Count outward. One step reaches ten people, two steps about a hundred, three about a thousand — the reachable set multiplies, so it swallows the population after roughly the number of steps it takes for ten-to-the-power-of-something to exceed the population size. For a billion, that is about nine. Shallow, but with essentially no clustering: your ten random contacts are scattered strangers who will almost never know each other.

So the extremes trade off. Do they have to? Watts and Strogatz asked in 1998 what happens between them: start from the ring, then take each edge and, with some small probability, rewire one end to a random person. Turn that probability up slowly from zero.

Here is the finding, and it is an asymmetry rather than a compromise. The typical path length collapses almost immediately — while the clustering barely moves. Ask why, and the mechanism is plain. Clustering is a local average: it asks, for each person, what fraction of their friend pairs are themselves friends. Remove one edge in twenty and you have removed one edge in twenty of the triangles; the average dips slightly. Path length is a global quantity, and one long-range shortcut does not help just its two endpoints — it becomes available to everyone in both neighbourhoods, cutting a huge detour for a large number of pairs at once. A handful of shortcuts therefore does an enormous amount of work while costing almost nothing in local structure.

That is the small-world regime: clustering near the lattice's, path length near the random graph's. Not a balance point, but a wide band where you get both.

Now, the famous evidence. In 1967 Milgram, and later Travers and Milgram, gave people in the American Midwest a packet addressed to a stranger in Boston, to be forwarded only to someone they knew on first-name terms. Among the chains that arrived, the median was around five intermediaries — the source of "six degrees". But the honest number to quote alongside it is the completion rate: 64 of 296 chains finished. A 2003 email replication by Dodds, Muhamad and Watts started roughly 24,000 chains and completed a few hundred. Most chains simply die of indifference, and a median computed only over survivors is biased toward the short ones.

Which raises the sharper question. The rewiring argument shows short paths exist. Milgram's letters show something else: that people, seeing only their own contacts and knowing nothing of the global map, can find one. Those are not the same claim, and the second does not follow from the first. Kleinberg showed in 2000 that it can fail — in a lattice where long-range links are chosen with probability falling off as a power of distance, a person forwarding greedily toward the target succeeds quickly only when that power matches the lattice's dimension. Tune it either way and short paths still exist, but no local strategy locates them.

A few refinements hold the picture together.

"Six degrees" is a slogan, not a measured constant. The number depends entirely on which network you mean — acquaintance, email, coauthorship, Facebook friendship — and on how you handle the chains that never arrive. Treat it as an order of magnitude: short, not one or two.

Short paths are also less surprising than they feel, because the shock comes from linear intuition. We expect distance to add; in a branching network, reach multiplies. Multiplication of even a modest branching factor exhausts a planet quickly. The genuinely surprising part of Watts and Strogatz is not that random graphs are shallow — that was known — but that so little randomness is needed to buy the shallowness, and that the local texture survives the purchase.

Two honest qualifications. Real social networks are not the Watts-Strogatz ring: their degrees are wildly unequal, with a few extremely well-connected people, and hubs shorten paths by a mechanism of their own that the rewiring model does not contain. And "small world" is a description of two measured quantities together — high clustering, short paths — not an explanation of how a given network came to have them.

• Kleinberg's navigability condition, and why only one exponent makes greedy search work.
• Scale-free degree distributions, and how hubs shorten paths differently from random rewiring.
• Why weak ties — the acquaintances, not the close friends — carry most of the shortcuts.

Every term the collection defines is gathered in the glossary.