Four degrees of separation

By Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, Sebastiano Vigna. Web Science Conference, 2011

592 citations recorded by the source corpus.

Frigyes Karinthy, in his 1929 short story "Láncszemek" (in English, "Chains") suggested that any two persons are distanced by at most six friendship links.1 Stanley Milgram in his famous experiments challenged people to route postcards to a fixed recipient by passing them only through direct acquaintances. Milgram found that 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 (≈ 721 million users, ≈ 69 billion friendship links). The average distance we observe is 4:74, corresponding to 3:74 intermediaries or "degrees of separation", 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.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f4b0fb2595ded37509b8f939d054ea5c58a1f2f8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review (2012, unknown): “74 edges (Blackstrom et al., 2011).”
egoSlider: Visual Analysis of Egocentric Network Evolution (2016, background): “Though the alter numbers in online social networks might be much larger than the ones in traditional social networks [10], the scalability of the Alter Timeline View can be improved by aggregating the alter bars as rectangles and alter curves as flows.”
A Review of Facebook Research in the Social Sciences (2012, unknown): “…users’ friends were most likely to be of a similar age and from the same country; (d) the average number of Facebook friends in the United States was 214 (Backstrom, 2011; Backstrom et al., 2011; Ugander et al., 2011), somewhat higher than the worldwide average of 130 reported by Facebook (2012).”
The Economic Consequences of Social Network Structure (2017, methodology): “This kind of experiment has been implemented more recently via email (Dodds, Muhamad and Watts (2003)), and on social media sites (e.g., Backstrom et al (2012)).”
X-Stream: edge-centric graph processing using streaming partitions (2013, background): “[15] report that the average path length between two people in the 721 million strong Facebook social network is smaller than 5.”
Web Data Extraction, Applications and Techniques: A Survey (2012, unknown): “Keywords: Web Information Extraction, Web Data Mining, Business Intelligence, Knowledge Engineering, Knowledge-based Systems, Information Retrieval ∗Corresponding author Email addresses: ferrarae@indiana.edu (Emilio Ferrara), pdemeo@unime.it (Pasquale De Meo), gfiumara@unime.it (Giacomo Fiumara), ro”
Do the Young Live in a "Smaller World" Than the Old? Age-Specific Degrees of Separation in a Large-Scale Mobile Communication Network (2016, methodology): “In this work, rather than employing the sampling and probabilistic methods used in previous work [4, 23], we instead leverage a large computing cluster to determine the average shortest paths between all pairs of users, that is n× (n− 1)/2 pairs, where n is the number of users in each network.”
Handbook of Big Data (2016, methodology): “For example, it can help us learn new things about the world, including both the chemical and biological sciences [7,8] as well as results in the social and economic sciences such as the Facebook study that showed that any two people in the(ir) world can be connected through approximately four inter”
Diffusion Improves Graph Learning (2019, background): “1 due to the “four/six degrees of separation” in real-world graphs [5].”
Evolution of social-attribute networks: measurements, modeling, and implications using google+ (2012, background): “Third, we observe that assortativity of Google+ social network is neutral while many other social networks own positive assortativities.”
Information network or social network?: the structure of the twitter follow graph (2014, methodology): “Our ﬁndings are contrasted with studies of other social networks: Facebook [1, 14] (721m vertices, 68.7b undirected edges) and the network from users of MSN Messenger [8, 13] (180m vertices, 1.3b undirected edges).”
The Anatomy of the Facebook Social Graph (2011, methodology): “For the technical details behind these calculations, we refer the interested reader to a separate paper concerning the compression and traversal of the Facebook graph [27].”
Random Graphs and Complex Networks (2016, background): “In the Facebook network nodes represent the users and they are connected if they are friends on the social media platform Hyves was a Dutch social media platform.”