Source-linked AI summary
Four Degrees of Separation
Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, Sebastiano Vigna
TL;DR
The paper asks how short and dispersed paths are in the world’s largest electronic social network, extending Milgram-like distance measurement beyond earlier scales. Using HyperANF on Facebook and geographic or temporal subgraphs, it finds an average distance of 4.74, or 3.74 degrees of separation, with spid 0.09.
Problem
The paper addresses the limited scale of prior social-network distance measurements and the open question of Facebook’s distance-distribution dispersion.
Method
The authors use HyperANF to approximate neighbourhood functions and derive distance distributions for the complete Facebook graph and 29 geographically or temporally restricted graphs.
Results
4.74 is Facebook’s average distance, corresponding to 3.74 degrees of separation, while its spid is 0.09, well below one.
Takeaways & Limitations
Facebook is a small-world graph with short paths between many pairs, and its spid supports the view that proper social networks have dispersion well below one.
Takeaways & Limitations
The actual 30 studied graphs cannot be publicly released for nondisclosure reasons, although derived structural and probabilistic data are distributed.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops world-scale measurements of Facebook’s graph-distance distribution to test social-network structure and the “six degrees” idea. It finds Facebook’s average distance is 4.74 and its dispersion is far below one.
- Method: HyperANF enabled accurate study of distance distributions in graphs orders of magnitude larger than previously feasible.The tool builds on graph compression and diffusive computation.
- Motivation: The study addresses whether distance-distribution statistics can distinguish proper social networks from other complex networks such as web graphs.Distance distributions can reject models that match local features such as in-degree distributions.
- Scale: The Facebook analysis covered approximately 721 million active users and 69 billion friendship links, making it a vastly larger Milgram-like experiment than earlier attempts.The collaboration was motivated by testing the spid hypothesis and measuring Facebook’s graph distance at unprecedented scale.
- Findings: 4.74 is the average distance of the current Facebook graph, corresponding to 3.74 degrees of separation.The paper defines degrees of separation as distance minus one.
- Findings: 0.09 is Facebook’s spid, corroborating the conjecture that proper social networks have spid well below one.The spid is the variance-to-mean ratio of the distance distribution.
2 Related work
The paper situates its shortest-path analysis within Milgram’s routing experiment and prior large-network studies. It emphasizes that shortest-path distance differs from routing-path length and that geographic location affects observed path length.
- Milgram: Milgram’s experiment asked whether randomly selected individuals could be linked using varying numbers of intermediaries.The study framed this as the probability distribution of minimum intermediary counts.
- Geography: Geographic location affected average path length in Milgram’s experiment, whereas profession did not show the same effect.The paper uses geographic restrictions as a relevant comparison for Facebook subgraphs.
- Comparison: The authors measure shortest paths rather than Milgram-style routing paths because routing length is an upper bound on shortest-path distance.Milgram’s result also tested whether people could exploit the network’s smallness when routing messages.
- Prior large graphs: A Microsoft Messenger communication graph with 180 million nodes and 1.3 billion edges had average distance 6.6, or 5.6 intermediaries.The paper notes that this graph connects people who communicated directly, not necessarily Facebook friends.
- Prior work: Prior social-network distance studies used graphs at least two orders of magnitude smaller and relied on sampling techniques.The paper notes that sampling is not easily applicable to directed networks that are not strongly connected.
3 Definitions and Tools
The paper defines neighbourhood functions and derives distance distributions from them, then uses HyperANF and compressed graph representations to estimate these quantities at very large scale. It addresses estimator variability and bias with repeated runs and jackknife estimates.
- Definitions: The neighbourhood function NG(t) counts reachable ordered node pairs within at most t steps and supports deriving the distance distribution.The resulting distribution gives the fraction of reachable pairs at each exact distance.
- Tools: HyperANF approximates the neighbourhood function of very large graphs using diffusion-based computation and WebGraph’s compressed representation.WebGraph provides a compressed but quickly accessible graph representation.
- Ball expansion: HyperANF incrementally computes balls B(x,r) from B(x,0) = {x} through sequential graph scans.The method addresses the need to access prior-radius sets during computation.
- Approximation: HyperLogLog counters approximate ball sizes by tracking hashed elements across small registers and aggregating the resulting estimates.The counters are designed to answer size questions reliably rather than represent the sets exactly.
- Computation: The systolic approach avoids recomputing unchanged balls, allowing HyperANF to compute the entire distance distribution without arbitrary termination conditions.Previous approaches lacked provable accuracy under arbitrary stopping rules.
- Accuracy: The HyperANF output is asymptotically almost unbiased for the neighbourhood function, with relative standard deviation bounded by the counter estimates.For m ≥16, the stated bias term satisfies |δ1(x)| < 5 · 10^-5.
- Error control: 64 registers were used for most graphs, while the two largest Facebook graphs used 32 registers; runs were repeated to obtain uniform relative standard deviation.The corresponding relative standard deviations were 0.1325 and 0.187.
- Limitations: Relative neighbourhood-function error becomes absolute error in the distance distribution, and normalization introduces nonlinear bias.The authors use jackknife estimation to reduce bias and estimate measurement standard errors.
4 Experiments
The experiments analyze Facebook graphs across regions and time using compressed representations and probabilistic distance-distribution methods. Layered label propagation substantially improves locality and compression, while the resulting gap distributions reveal structured clustering alongside a small residual random core.
- Experimental setup: The study analyzes active-user Facebook graphs from 2007 onward, covering the entire network and USA, Italian, Swedish, and combined Italian–Swedish regional subgraphs.Historical graphs use currently active users who were registered on January 1 of each year; geographic location is based on current geo-IP location.
- Experimental setup: HyperANF estimates neighbourhood functions and distance distributions, while WebGraph stores the analyzed graphs in compressed form for repeated scans.Multiple runs provide higher-precision estimates, with jackknife estimates and associated standard errors reported for derived values.
- Compression and locality: 30% graph-size reduction after layered label propagation suggests that the permutation discovers several significant clusters.LLP computes clusterings at different granularities and orders nodes to increase locality and similarity; applying it to the current Facebook graph required ten days.
- Compression and locality: After LLP permutation, successor-gap distributions become mostly monotonically decreasing, with a small bump at 23 indicating a residual core of graph randomness.Smaller gaps indicate higher locality; the renumbered graph instead has a local maximum at 2 and most probability mass around 20–21, slightly below the ≈23 information-theoretical lower bound.
- Compression and locality: Successors represented by copying increase from 9% to 18%, while disabling copying increases graph size by only ≈5%.The latter result is reported as supporting faster random access when copying is disabled.
- Compression and locality: The reported compression ratio is around 53%, but reduced LLP clustering and limited iterations constrain how much structure the permutations can discover.The authors also note that larger graphs incur coding costs dependent on absolute gap magnitudes, which the lower bound does not capture.
4.2 Running
Running HyperANF on the largest graphs required keeping counters in main memory to reduce excessive I/O. The current whole Facebook graph used about 27 GiB for its counters.
- Running: HyperANF stores counters for B(x, r−1) and B(x, r) in main memory because memory-mapped graphs would otherwise incur excessive I/O.The current whole Facebook graph used 32 registers, requiring about 27 GiB for counters.
4.3 General comments
The paper tracks Facebook's historical connectivity and distance-related structure, while cautioning that early snapshots were not representative of the underlying human social-link structure.
- Distance structure: Figure 2 reports current-graph distance distributions as probability mass functions truncated at distance 10.
- Historical data: 2007–2008 Facebook data are useful for observing network evolution but are not representative of the underlying human social-link structure.Facebook was initially highly disconnected; measurements stabilized after 2009, with essentially all pairs reachable.
- Network evolution: The average degree of the considered graphs grows relatively quickly over time.
- Distance structure: Figure 3 presents the average-distance graph and refers readers to Table 6 for related values.
4.4 The distribution
Current Facebook distance distributions are concentrated at short distances, while network connectivity changes over time through increasing average degree, decreasing density, and geographic effects.
- Distance distribution: Regional graphs concentrate around distance four, whereas the whole Facebook graph concentrates around distance five.The it and se distributions place significantly less mass at distance five than itse and us.
- Distance distribution: The distance distribution quickly becomes extremely concentrated, according to variance data from Table 7 and Figure 4.
- Average degree and density: The average degree grows relatively quickly over time, but sparse temporal sampling makes power-law conclusions unreliable.The us graph, for example, shows a change in slope on the loglog-scaled plot.
- Average degree and density: Network density decreases over time, with sparsification especially evident in the more complete Facebook and US graphs.
- Average degree and density: Geographical concentration increases density, with regional graph lines ordered by concentration and the Facebook graph lowest.
4.6 Average distance
The paper measures average distances between reachable Facebook users, finding short paths, geographic effects, and stabilization over time despite declining density.
- Measurement choice: Average distance is distinguished from effective diameter, which uses the 90% percentile of the distance distribution.The authors prefer average distance because it is a parameterless, standard distributional feature.
- Average distance: 4.74 is the current Facebook graph’s average distance between reachable pairs.This measure excludes unreachable pairs and matches the average-distance measure used by Travers and Milgram.
- Geographic subgraphs: Average distance depends more on users’ geographical closeness than on network size.The it and se graphs have similarly lower averages, while the itse graph has a higher average.
- Evolution over time: Facebook’s average distance decreased during rapid growth but now appears to be stabilizing.This occurred while density steadily declined, illustrating a smaller-world pattern in the observed graphs.
- Average distance: 92% of reachable user pairs lie within distance five, or four degrees of separation.The percentage is calculated relative to reachable pairs, not all possible pairs.
4.7 Spid
The spid measures dispersion in the distance distribution and is used to distinguish properly social networks from web-like graphs. Facebook’s spid is generally well below one, with little overall correlation to average distance.
- Definition: The spid is the variance-to-mean ratio σ2/µ of the distance distribution.Values below one indicate underdispersion; values above one indicate overdispersion.
- Facebook result: Facebook’s spid is well below one except in highly disconnected regional networks from 2007–2008.This supports the conjecture that proper social networks have spid below one.
- Correlation: Kendall’s τ is −0.0105 for the overall correlation between average distance and spid.The authors characterize the relationship across their graph collection as generally weak.
- Correlation: Within individual networks, apparent correlations arise because variance and average distance change together, not because spid directly tracks distance.The reported relationship between spid and average distance is inverse, while variance changes in the same direction as average distance.
4.8 Diameter
The paper combines approximate HyperANF bounds with a parallel exact-diameter strategy. Results show concentrated short-distance distributions alongside rare, much longer paths.
- Approximate bounds: HyperANF run length supplies a lower bound on graph diameter, but cannot provide exact diameter values.Hash collisions can make registers stabilize before the diameter, never after; the bounds therefore lack statistical guarantees.
- Exact computation: The exact-diameter computation uses a highly parallel implementation of the iFUB algorithm for undirected graphs.The approach refines lower and upper bounds by examining graph fringes until they match.
- Exact computation: The iFUB procedure starts with a double sweep, then uses a midpoint’s eccentricity and iterative fringe searches to tighten diameter bounds.A farthest-node pair gives a lower bound, while midpoint and fringe eccentricities provide upper and lower bounds.
- Computation: The multicore implementation discovered the current us graph’s diameter in about twenty minutes and required ten hours for Facebook.The us graph fit in main memory using LLP compression, while Facebook required a machine with 1 TiB of RAM.
- Results: The distance distribution has a low average and is concentrated, yet rare node pairs remain much farther apart.For the current Facebook graph, long paths occur in small and sparsely connected regions.
4.9 Precision
The paper examines theoretical and empirical precision limits in approximate distance-distribution computations. Although tail errors are difficult to bound theoretically, error stabilization explains the observed accuracy.
- Theoretical precision: Distance-distribution estimates can incur significant errors because relative neighborhood-function bounds become absolute errors in the distribution’s small tail values.This makes strong theoretical guarantees difficult for average distance and related statistics.
- Empirical precision: The derived data distribution is empirically extremely concentrated despite weak theoretical bounds.The authors use this concentration to contextualize the practical accuracy of their measurements.
- Empirical validation: The paper illustrates this accuracy mechanism with the evolution of empirical relative error in a HyperANF run on dblp-2010.The example uses a relative standard deviation of 9.25%.
- Error mechanism: In the tail, approximate counters behave similarly and their relative error stabilizes to an almost fixed value.Because the variation of relative error quickly converges to zero, neighborhood-function relative error transfers practically to the distance distribution.
- Scope: The precision observations remain applicable to diffusion-based algorithms using approximate, statistically dependent counters, including ANF.This extends the authors’ practical explanation beyond HyperANF alone.
5 Conclusions
The paper analyzes the world’s largest electronic social network from multiple viewpoints, combining structural compression with graph-distance analysis. Facebook exhibits short paths and strong geographic locality, while its large scale enables a major Milgram-like experiment.
- ≈721 million active users and ≈69 billion friendship links define the Facebook graph studied.
- Layered labelled propagation increases social-network locality by permuting nodes.
- 4.74 is Facebook’s average distance, corresponding to 3.74 degrees of separation.
- Geographically restricted networks have smaller average distances, showing geography strongly shapes the overall network structure.
- Milgram’s intermediaries measured routing paths, whereas this study focuses on shortest-path distances.