Six Handshakes, Give or Take

In 1967 the psychologist Stanley Milgram ran an experiment through the post. He gave letters to people in Wichita, Kansas, and in Omaha, Nebraska, meant for a stranger in Massachusetts: in one version the wife of a divinity student in Cambridge, in another a stockbroker who worked in Boston. The rule was that you could send it straight to the target only if you knew them personally. Otherwise you sent it to someone you knew on first-name terms who seemed more likely to know them, and that person did the same.

Some of the letters arrived, and the chains that arrived were short. In the fullest published version, in 1969, the average completed chain had about five intermediaries. Six degrees of separation, which John Guare made the title of a play in 1990, comes from there, although the Hungarian writer Frigyes Karinthy had a character propose much the same idea in a short story in 1929.

There are two things wrong with the popular version, and then one thing right with it that is stranger than the popular version.

The first problem is attrition. In that 1969 study, 64 of 296 chains reached the target. The rest stopped somewhere, because somebody could not be bothered, or did not know whom to try, or lost the letter. An average over the chains that finished is an average over the successes, and a chain that died might have been on its way to being a long one. Judith Kleinfeld, going back over Milgram's work in 2002, argued that the evidence was much thinner than the slogan. Later studies run by email found chains of similar length and similar losses. The short paths seem real. The number six is a rough figure, not a constant of human nature.

The second problem is subtler: short paths are not surprising at all. Suppose everyone had a hundred acquaintances chosen completely at random from the whole population. Then you reach a hundred people in one step, roughly ten thousand in two, a million in three, and the whole planet in five or so. In a random network, distances grow with the logarithm of the size, which is to say hardly at all. Short paths are what you get for free.

What is not free is that real social networks are not random. They are clustered: two of your friends are far more likely to know each other than two people chosen at random. Clustering is what makes a social world feel like a set of villages, and a world of villages ought to be large. A message passed from neighbour to neighbour in a world like that crawls.

So the real puzzle is how a network can be clustered like a set of villages and small like a random graph at the same time.

Duncan Watts and Steven Strogatz answered it in 1998, with a model that is almost embarrassingly simple. Start with a ring of people, each linked to their nearest few neighbours. That network is highly clustered and large: getting across it takes many steps. Now take each link and, with some small probability, rewire one end to a person chosen at random. With very little rewiring the clusters survive, because nearly all links are still local. But the distances collapse, because each rewired link is a shortcut between distant parts of the ring, and a few shortcuts serve everybody near either end of them. Across a wide range in between, the network is both clustered and small.

They then went looking, and found the same shape in the nervous system of the nematode worm C. elegans, in the power grid of the western United States, and in the network of film actors who have appeared together. Small worlds were not a quirk of acquaintance. They were what you get whenever mostly local structure has a few long links.

There is one more step, and it is the one that makes Milgram's result genuinely remarkable. Short paths existing is not the same as people finding them. Milgram's participants had no map of the network. Each knew only their own contacts, and something rough about where the target lived and what they did. Jon Kleinberg showed in 2000 that in most networks with shortcuts, that kind of local, greedy forwarding takes a long time to find the short paths, even though they are there. It works quickly only when the long links are arranged in one particular way, becoming rarer with distance at a specific rate.

That the letters arrived at all, guided by nothing but each holder's guess about who was closer, suggests that human acquaintance networks have something like that structure. It is a finer claim than six degrees, and a better one: the world is not only small, it is small in a way that people can use.