Abstract
Frigyes Karinthy, in his 1929 short story "Láancszemek" ("Chains")
suggested that any two persons are distanced by at most six friendship links.
(The exact wording of the story is slightly ambiguous: "He bet us that, using
no more than five individuals, one of whom is a personal acquaintance, he could
contact the selected individual ...". It is not completely clear whether the
selected individual is part of the five, so this could actually allude to
distance five or six in the language of graph theory, but the "six degrees of
separation" phrase stuck after John Guare's 1990 eponymous play. Following
Milgram's definition and Guare's interpretation, we will assume that "degrees
of separation" is the same as "distance minus one", where "distance" is the
usual path length-the number of arcs in the path.) Stanley Milgram in his
famous experiment challenged people to route postcards to a fixed recipient by
passing them only through direct acquaintances. The average number of
intermediaries on the path of the postcards lay between 4.4 and 5.7, depending
on the sample of people chosen.
We report the results of the first world-scale social-network graph-distance
computations, using the entire Facebook network of active users (\approx721
million users, \approx69 billion friendship links). The average distance we
observe is 4.74, corresponding to 3.74 intermediaries or "degrees of
separation", showing that the world is even smaller than we expected, and
prompting the title of this paper. More generally, we study the distance
distribution of Facebook and of some interesting geographic subgraphs, looking
also at their evolution over time.
The networks we are able to explore are almost two orders of magnitude larger
than those analysed in the previous literature. We report detailed statistical
metadata showing that our measurements (which rely on probabilistic algorithms)
are very accurate.
Description
Four Degrees of Separation
Links and resources
Tags
community