Everyone is six steps away

In the 1960s Stanley Milgram asked a few hundred strangers to get a letter to one man they had never met, passing it only through people they knew personally. The letters that arrived needed about five intermediaries. That is where "six degrees of separation" comes from, and it measured something slightly different from what the phrase claims.

The chain letter

A 2011 paper by Backstrom, Boldi, Rosa, Ugander and Vigna retells the experiment before repeating it at a scale Milgram could not. He selected 296 volunteers. Each was asked to send a message to a target: a stockholder who lived in Sharon, Massachusetts, a suburb of Boston, and worked in Boston. Nobody could mail the target directly unless they knew him. They had to send it to an acquaintance they thought was closer, who did the same.

Most chains died on the way. Only 64 reached the target: 22% of the 296 starters. (The 29% you may have seen is the same 64 out of the 217 packets that were actually sent.) In those 64 chains the average number of intermediaries was 5.2. Starters living in Boston needed 4.4. Nebraskans picked at random, with no special access to the investment business, needed 5.7, which rounds up to six.

Why a short chain is surprising

In our town, most of the people you know live near you and know each other. If everyone knew only their neighbours, a letter would have to crawl across the country one town at a time, and the number of steps would grow in proportion to the distance.

What breaks that is a small number of links that jump a long way: the cousin in another state, the college friend who moved. Each one is rare. But you are only a few steps from a great many people, and some of them hold a long link. So the number of people within reach multiplies with every step, and a short path turns up long before you run out of steps.

A short path exists; can anyone find it?

A graph is a set of points with lines between some pairs. The distance between two points is the fewest lines you must cross to get from one to the other. Averaged over every pair, it says how small the network is.

In our town, with no far links, the average distance grows in step with the population: 12.9 steps for 100 people, 200.4 for 1600. Give every 100 people 50 far links — one far friend per person on average — and it drops to 3.6 steps at 100 people and 6.1 at 1600. The town grew sixteen times; the average rose by about 0.6 steps each time the town doubled.

The paper makes the point that matters here. Milgram measured the chains people found. The people forwarding his letters did not necessarily send them along a shortest path, so his 5.2 is an upper bound on the true distance, not the distance itself. Backstrom and colleagues read that generously: the letters show not only that the world is small, but that the people in it can exploit its smallness.

The interactive shows why a found route is only an upper bound. A letter-writer knows their own friends and a few facts about the target, and can rarely see further than their own acquaintances. Our local rule hands the letter to whichever friend lives nearest the target. In the same 1600-person town it takes 24.6 steps on average, four times the shortest path. The rule can only see the friends of whoever is holding the letter, so a far link belonging to anyone else may as well not exist.

Four degrees, measured

The paper then computed distances directly, on the entire Facebook network of active users as of May 2011: about 721 million people and 69 billion friendship links. There is no forwarding and no guessing, so no upper bound: an approximation that expands outward from every node at once estimated the whole distance distribution. The average distance was 4.74, with a standard error of about 0.02 — 3.74 intermediaries. That gives the paper its title, "Four Degrees of Separation." Run across the years, the average fell through Facebook's fastest-growing period and now appears to be levelling off, and the network's density — the share of all possible links that actually exist — went steadily down. The 2007 and 2008 graphs carry a caveat: Facebook was still rather fragmented then, so the paper uses those years to trace the platform's growth, but does not treat them as a picture of human social ties.

In short

Milgram's letters took an average of 5.2 intermediaries, counting only the chains that arrived, and routes people found by guessing are only an upper bound on the shortest one. In our town a few long-range links are enough to keep the true distance small, because the number of people in reach multiplies at every step. In the May 2011 Facebook graph, the average was 3.74 intermediaries, with a standard error of about 0.02.