Six Degrees of Separation at World Scale: Exact Shortest Paths in Acquaintance Networks of 8.59 Billion People

A graph that is a function rather than a data structure

An acquaintance network of 8.59 billion people with 150 contacts each has 644 billion edges. Stored as a conventional adjacency structure that is on the order of ten terabytes, which is why the two published world-scale distance computations (Backstrom et al. 2012 on 721 million Facebook users, Leskovec and Horvitz 2008 on 180 million Messenger users) both used approximation algorithms over a materialised graph, and why neither covered the whole human population.

The approach here never builds the graph. Instead, “who does person u know?” is answered by arithmetic. A keyed pseudo-random permutation, built as a four-round Feistel network over the smallest power-of-two domain containing the population and folded back onto the exact population size by cycle walking, turns node identifiers into pseudo-random images. Four Feistel rounds over a pseudo-random round function give a strong pseudo-random permutation (Luby and Rackoff 1988), and cycle walking is the standard way to restrict such a permutation to an arbitrary domain size (Black and Rogaway 2002).

The step that makes an undirected graph possible is an involution. For a keyed permutation sigma of an even-sized domain, define

partner(u) = sigma_inverse( sigma(u) XOR 1 )

Pairing up images that differ only in their lowest bit is a perfect matching of the domain; pulling it back through sigma makes that matching uniformly random. The map is its own inverse and has no fixed point, so u discovers v as a neighbour exactly when v discovers u, with nothing stored. A union of such matchings over a stub space reproduces the configuration model (Molloy and Reed 1995) with an arbitrary degree distribution, and matchings taken inside nested blocks reproduce the hierarchical social geometry of Watts, Dodds and Newman (2002).

Figure 1: Storage for an explicit adjacency structure against population, at 150 acquaintances each, compared with the largest working set actually measured across the campaign’s 942 tasks. The vertical marker is the simulated world population and the horizontal marker is the measured peak.

Distances are then exact. A bidirectional breadth-first search expands whichever frontier is smaller and stops when the best witnessed path is no longer than the sum of the two explored radii. That rule is sound: if every node within r_s of the source and r_t of the target has been visited, any path of length at most r_s + r_t must pass through a node that both searches have seen, so the best witness is the true geodesic. Pairs whose search exceeds its budget return a proved interval rather than being discarded, and the reported probabilities count only outcomes that are decided in one direction or the other.

The claim needs about a hundred acquaintances, and we have more than that

The first question is how many contacts each person needs for the claim to be true at all, in the most favourable case: a world where each person’s acquaintances are drawn uniformly from the whole population.

Figure 2: Probability that a uniformly random pair of the 8.59 billion is within six hops, against the number of acquaintances each person has, for two degree distributions. Bands are 95 % Wilson intervals and are narrower than the lines over most of the range. The vertical marker is the smallest tested value at which the claim holds for more than 99 % of pairs.

The transition is sharp and it sits below the empirical range. Scale-up survey methods place the mean personal network well to the right of the threshold, by two independent estimators (McCarty et al. 2001). On the number of acquaintances alone, therefore, the claim is not merely true but true with room to spare, and this is presumably why the folklore feels robust.

Figure 3: Exact distance distributions for five acquaintance counts in the well mixed world. Each series is the pooled histogram over all sampled pairs for that configuration. The vertical marker is the six-hop claim.

The distributions are narrow: almost all of the mass sits on two adjacent integers. This matters for interpreting the claim, because it means there is no long tail of moderately distant pairs to argue about. A configuration either puts essentially everybody inside six hops or essentially nobody, and the interesting question is which side of that line a realistic population falls on.

Distance against population, measured rather than extrapolated

Because the graph costs nothing to store, the same model can be measured at every scale from eight thousand people to the whole world, which removes the usual need to fit a curve on small graphs and extend it.

Figure 4: Mean exact shortest-path length against population for two models with 150 acquaintances each, measured at eleven sizes spanning six orders of magnitude. The horizontal marker is the six-hop claim; the vertical marker is the world population.

Two features are worth noting. The well mixed model reaches the world population at roughly five hops and never approaches the limit. The model with realistic locality follows a steeper logarithm and arrives at the world population sitting almost exactly on six, which is the least comfortable place for a claim to sit: the answer becomes sensitive to parameters that are not well pinned down empirically.

The measurement also provides a check on the standard practice of extrapolating from graphs small enough to hold in memory. Fitting the mean against the logarithm of population on classical graphs of at most two million nodes, and extending the fit to 8.59 billion, can be compared against the exact value.

Figure 5: Extrapolation from graphs of at most 2.1 million nodes against the exact value measured at 8.59 billion, for two model families. The extrapolation is a linear fit of mean geodesic on the logarithm of population.

The fitted and exact values agree to within a tenth of a hop. This is a reassuring result for the wider literature, most of which has no alternative to extrapolation, and it is worth stating plainly because it could easily have come out otherwise.

Locality raises the price of the claim

The well mixed model is a poor description of human contact. Real acquaintance networks are clustered, because one’s friends tend to know one another, and geographically concentrated. The relevant empirical estimate comes from Liben-Nowell et al. (2005), who found on half a million LiveJournal users that about one third of friendships are independent of geography while the remaining two thirds follow a rank-based rule in which the chance of befriending someone falls with the number of people who are closer.

The model here carries a parameter for exactly this: how quickly the number of ties falls off as social distance grows. A value of 1.0 spreads a person’s contacts evenly across all scales, from household to planet, which is the condition Kleinberg (2000) identified as the navigable one. Values below 1.0 concentrate contacts locally.

Figure 6: Share of pairs within six hops against how strongly ties concentrate locally, at five fixed acquaintance counts. Lower values on the horizontal axis mean more local contacts. Every series holds the total number of acquaintances fixed, so the only thing varying is where those acquaintances live.

At 150 contacts, which is within the empirical range, moving from evenly spread ties to moderately local ones takes the claim from holding for every pair to holding for a little over half of them. The number of acquaintances is unchanged throughout. What changes is whether those acquaintances are spread across the world or concentrated near home.

The natural check is whether the configurations that satisfy the claim also look like human networks by an independent measure. Clustering, the probability that two of a person’s contacts know each other, is the standard one, and it is high in real social networks and near zero in well mixed ones.

Figure 7: Every world-scale configuration in the campaign, positioned by its clustering coefficient and by the share of pairs it puts within six hops. The shaded band is the range of clustering reported for human social networks. Configurations are coloured by the family of model they belong to.

Two things are visible. Configurations with almost no clustering satisfy the claim comfortably, and configurations inside the realistic band are spread across the entire vertical range, from certainty to zero. Realistic clustering is therefore not by itself fatal to the claim, which is a weaker statement than the one the previous figure invites. What the band contains is a genuine disagreement, and resolving it requires asking which configurations inside it succeed.

What rescues the claim in a clustered world

Four configurations settle the question. All four have clustering in or just below the range observed in human networks, and they differ only in how many contacts people have and whether a small minority of very well-connected people exists.

Figure 8: Four configurations with realistic clustering, differing only in contact count and in whether a heavy-tailed global layer is present. Bars give the share of pairs within six hops, with the measured mean contact count and clustering coefficient beside each. Three of the four are fully decided; the 20 % hub variant leaves 3.5 % of pairs undecided.

Adding contacts works, and so does adding hubs. Raising the contact count from about 120 to about 250, holding the tie geometry fixed, takes the claim from holding for a little over half of pairs to holding for all of them, with a lower confidence bound of 99.9 %. Alternatively, diverting one twentieth of an unchanged contact budget into a heavy-tailed global layer achieves the same thing at 122 contacts.

The second route is the more interesting one, and it is specific to clustered worlds. In the well mixed population of the earlier figures, heavy tails bought roughly half a hop. Here the same structural feature is decisive, because in a clustered world a hub is the only thing that reliably crosses between distant communities. Since the survey estimate of the mean personal network lies above the contact count at which the plain model already succeeds, the topological claim is most likely true of the human population for typical pairs, by either mechanism or both.

Two structural features that help, and one that does not

Before turning to the parts of the claim that fail, it is worth isolating what helps. Two candidates are prominent in the literature: heavily unequal contact counts, which create hubs, and a small number of purely random long-range ties added to an otherwise local world.

Figure 9: Mean shortest path against the variance of the contact-count distribution, holding the mean at 150 acquaintances. Higher values on the horizontal axis mean a small number of people with very many contacts. Labels give the distribution and its shape parameter.

Heavy tails do shorten paths, consistent with the analytic result that scale-free networks are ultra-small (Cohen and Havlin 2003), but in a well mixed population the effect is bounded: about one hop across a twelvefold change in the second moment of the contact distribution. That modesty is exactly why the preceding section matters. The same feature that is nearly irrelevant when everybody mixes freely becomes decisive once contacts are concentrated locally.

Figure 10: A one-dimensional world in which each person knows their nearest neighbours along a ring, plus q ties to uniformly random strangers, holding total contacts at 150. Bars give the share of pairs within six hops and labels give the mean shortest path.

This is the Watts and Strogatz (1998) mechanism measured at world scale, and the quantitative answer is less generous than the qualitative story suggests. One or two random ties per person, the regime usually illustrated, leaves almost every pair beyond six hops at this population size. Twenty are needed.

The claim is universal, and universal claims are decided by their exceptions

Everything above concerns typical pairs. The claim as stated is about any two people, which makes it hostage to whoever is least connected. Some people have no contacts outside their immediate community: this is true of the very old, of the institutionalised, of remote populations, and it was Kleinfeld’s central objection to the folklore (Kleinfeld 2002) that the great majority of Milgram’s chains never arrived at all.

Two versions are distinguishable. In the first, whole communities are cut off. In the second, isolated individuals are scattered through an otherwise connected population, so their neighbours still have distant ties.

Figure 11: Effect of a population fraction with no ties beyond their immediate locality, in two arrangements. The left panel gives the share of pairs within six hops; the right panel gives the share of pairs with no connecting path of any length.

The two arrangements fail differently and both fail. Cutting off whole communities creates pairs at infinite distance, not at seven or eight hops, and the fraction of affected pairs is roughly twice the isolated fraction because a pair is broken if either end is isolated. Scattering the same people through the population leaves everyone reachable, since their neighbours are not isolated, but adds enough hops to push a large share of pairs past six. For reference, Ugander et al. (2011) found 99.91 % of Facebook users in a single connected component, so even on a platform that requires connectivity to be useful, roughly one user in a thousand sits outside it.

What Milgram actually measured

The claim’s second reading is about search. A chain letter is not routed along a shortest path, because nobody can see one. It is routed greedily: each holder forwards to whichever of their contacts seems socially closest to the target. The simulation implements exactly this, with the target’s location known and no backtracking.

Figure 12: Distribution of chain lengths found by greedy forwarding in three worlds, all with the shortest-path distribution of the same population shown for comparison. Greedy chains are what a Milgram-style experiment can observe; geodesics are what the phrase ‘six degrees’ asserts.

The gap between the two mechanisms is the study’s largest single effect. In the same population where every pair is within six hops by shortest path, greedy forwarding produces a median chain roughly twice that length, and under moderately local ties the median moves into the tens of hops. Kleinberg’s analysis explains why: greedy search is efficient only when tie lengths are distributed across scales in one specific way, and a population that deviates from it in either direction becomes hard to navigate even though it remains topologically small.

Figure 13: Median greedy chain length for every combination of acquaintance count and tie concentration tested. Cells are annotated with the median hop count and the share of attempted chains that ever reached the target.

Completion rates collapse away from the navigable value in either direction. This reproduces the qualitative finding of the two field experiments: Travers and Milgram recorded 64 completed chains from 217 that were started (Travers and Milgram 1969), and the global email replication recorded 384 completions from 24,163 chains (Dodds, Muhamad and Watts 2003).

One consequence deserves its own figure, because it is the mechanism by which a real experiment overstates how short the world is. Dodds and colleagues measured a per-step forwarding rate of 37 %, which means a chain of length L survives with probability 0.37 raised to the L. Long chains are therefore systematically missing from the observed data.

Figure 14: Greedy chain lengths in a navigable world, as generated and as they would be observed after per-step attrition at the 37 % forwarding rate measured by Dodds, Muhamad and Watts. Attrition removes long chains preferentially, so the surviving sample is shorter than the population it is drawn from.

The observed distribution is shifted several hops left of the generated one. An experiment that reports the median of its completed chains is therefore reporting a biased statistic, and the direction of the bias is towards confirming the claim. Dodds and colleagues were explicit about this and corrected for it, arriving at a median of five to seven steps once attrition is accounted for. The uncorrected figure from the arrived chains alone is smaller.

Calibration against the one real measurement at this scale

A simulation of eight billion people cannot be validated directly, because no measurement of the human acquaintance graph exists. One adjacent measurement does: Backstrom and colleagues computed the distance distribution of the entire Facebook friendship graph, 721 million users and approximately 69 billion links, and found that 92 % of reachable pairs lie within five hops. Running the same models at that population gives a falsifiable target.

Figure 15: Mean shortest path for every model configuration run at 1.07 billion nodes, against the value Backstrom and colleagues measured on 721 million Facebook users. The vertical marker is their 4.74; bars are coloured by their distance from it.

The two closest configurations sit 0.10 and 0.11 hops from the measured value, which is a genuine check on the machinery rather than a fit, since none of the parameters were tuned to it. The interesting detail is which configurations succeed. Reproducing 4.74 requires either a well mixed population or one whose ties are spread evenly across social scales, that is, a clustering coefficient near zero.

This is worth dwelling on. The two large empirical results that are routinely cited as confirmation of six degrees were both measured on online platforms, and a friendship list is not an acquaintance network embedded in physical geography. Backstrom and colleagues noticed the same thing from the other direction, reporting materially shorter distances within single countries than across the whole graph and concluding that average distance depends on geographical closeness. The graphs that appear to vindicate the claim are precisely the graphs in which the mechanism that would refute it has been removed.

The answer depends on which network model is assumed

The final family is a control: six classical random-graph models, built explicitly in memory at four sizes each so that the implicit machinery can be checked against a graph that actually exists, and so that the spread across model families can be seen.

Figure 16: Mean shortest path against population for six classical models, all with 30 contacts per node except the lattices, which have eight. Built explicitly in memory with full breadth-first search from sampled sources. A uniform configuration model is omitted because it traces the Erdos-Renyi series to within 0.03 hops at every size.

The spread is the point. At two million nodes, holding contacts at thirty, the mean runs from 3.7 hops under a power-law configuration model to 9.8 under a lightly rewired ring, and the over-local lattice, which carries eight contacts rather than thirty, reaches 124. The two independently implemented well mixed models agree with each other to within 0.03 hops. Any statement about six degrees is therefore a statement about an assumed generative model, and the models cannot be distinguished by contact counts alone. They can be distinguished by clustering and by how tie probability falls with distance, which is exactly why those two parameters carry the result.

What the campaign cost, and what inspecting its output caught

Figure 17: Pairs evaluated by model family for the runs that compute one geodesic per sampled pair. The explicit control graphs are excluded because a single breadth-first search there returns every reachable pair at once, 22.3 billion in total, which is not a comparable unit of work.

Four defects in the implementation were found by looking at the output rather than by reading the code, and they are worth recording because each produced a plausible result rather than an error.

The explicit hierarchical builder rounded fractional tie counts down, so a level owed 0.98 ties per person received none. The world level disappeared and the graph separated into eight disconnected regions, which presented as 87 % of pairs being unreachable. Read without suspicion that is a finding, namely that locality defeats the small world, and it was a rounding bug. Correcting it brought the two independent implementations of the same model into agreement to within 0.03 hops.

Second, the frontier expansion sized its work batches by mean degree. In a heavy-tailed population a single batch can contain several individuals with a hundred thousand contacts, so a batch intended to hold six hundred thousand elements held tens of millions. That produced peaks of 10.4 GiB and tasks that ran into a forty-five minute wall clock limit. Sizing batches by actual cumulative degree took the worst configuration from timing out to seventy milliseconds per pair.

Third, the degree distribution itself was unphysical before it was truncated: a power law with exponent 2.1 rescaled to a mean of 150 implies individuals with roughly 1.4 million acquaintances. Truncating at ten thousand and re-solving the scale afterwards was necessary for the mean to remain where it was supposed to be.

Fourth, and most instructive for interpreting the tables above, a configuration can be undecidable rather than negative. In the most extreme corners of the locality sweep, more than nine tenths of pairs exhausted their search budget without either witnessing a short path or proving that none exists. Reporting the probability computed on the decidable minority would have overstated the claim, because short pairs resolve more cheaply than long ones. Those rows carry the undecided share explicitly, and the mean for such a configuration is reported as a proved lower bound rather than as an average over whatever happened to resolve.

What survives

The topological claim survives, and it survives less comfortably than its popularity suggests. A well mixed population needs about a hundred contacts each, which the human population has several times over. Concentrating those contacts locally, as human contacts are concentrated, raises the requirement to roughly two hundred and fifty, or leaves it near a hundred and twenty provided a small minority of people are very well connected. Survey estimates of personal network size sit above both thresholds, so the honest verdict on the topological claim is that it is probably true of typical pairs. It is true because two independent structural features happen to be present, not because six is a natural constant, and a population differing modestly in either respect would fail it.

The universal form of the claim is a different matter and it is false. Any non-trivial population of people without distant ties produces pairs at infinite distance rather than at seven or eight hops, and such populations exist.

The search claim, which is the one Milgram tested, holds in exactly one corner of the parameter space: 600 contacts each with ties spread perfectly evenly across social scales, where every chain arrives and the median found chain is six hops. One step away in any direction it fails. At 150 contacts with the same even spreading the median found chain is ten hops, and under moderately local ties it is thirty-one. The completion rates the two field experiments recorded, 29 % and 1.6 %, fall inside the range the geometry alone produces, without needing participant apathy to explain them.

What the phrase “six degrees of separation” gets right is that the human world is logarithmically small: distance grows like the logarithm of population, so multiplying the population by a thousand adds between one and two hops rather than a thousandfold. That is the substantive and surprising claim, it is robust across every model examined, and it is independent of the specific integer. The integer itself is an artefact of a particular graph, a particular experiment with a 29 % response rate, and a phrase that turned out to be more memorable than the measurement behind it.