CoChat
Sign Up
PreprintCited by 819Complex Network Analysis TechniquesGraph theory and applicationsGraph Theory and Algorithms

The Anatomy of the Facebook Social Graph

Open access
Ugander, Johan, Karrer, Brian, Backstrom, Lars, Marlow, Cameron·2011·arXiv
DOI 10.48550/arxiv.1111.4503arXiv 1111.4503
Open this paper in CoChat — free accountOpen PDF

Abstract

We study the structure of the social graph of active Facebook users, the largest social network ever analyzed. We compute numerous features of the graph including the number of users and friendships, the degree distribution, path lengths, clustering, and mixing patterns. Our results center around three main observations. First, we characterize the global structure of the graph, determining that the social network is nearly fully connected, with 99.91% of individuals belonging to a single large connected component, and we confirm the "six degrees of separation" phenomenon on a global scale. Second, by studying the average local clustering coefficient and degeneracy of graph neighborhoods, we show that while the Facebook graph as a whole is clearly sparse, the graph neighborhoods of users contain surprisingly dense structure. Third, we characterize the assortativity patterns present in the graph by studying the basic demographic and network properties of users. We observe clear degree assortativity and characterize the extent to which "your friends have more friends than you". Furthermore, we observe a strong effect of age on friendship preferences as well as a globally modular community structure driven by nationality, but we do not find any strong gender homophily. We compare our results with those from smaller social networks and find mostly, but not entirely, agreement on common structural network characteristics.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1111.4503

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Algorithm recommendations may have changed the structure of networks, increasing the frequency of triangles and enabling interaction between distant individuals.

    “Finally, algorithm recommendations may have changed the structure of networks, increasing the frequency of triangles (Salganik, 2019; Ugander et al., 2011) and enabling interaction between distant individuals (Bak-Coleman et al., 2021).”

    From Social Drivers and Algorithmic Mechanisms on Digital Media. (2024) · cites this paper as Ugander et al., 2011

    The Facebook Graph (p. 6) reports high clustering: many pairs of a user's friends are themselves friends, consistent with frequent triangles. The paper does not say algorithmic recommendations increased their frequency or changed the network's structure. The separate claim about interaction between distant individuals is cited to another source, not Ugander et al. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 49 · Cited by 819

Research works printed but not linked: 28

  1. [2]2. Wasserman S, Faust K (1994) Social Network Analysis. Cambridge: Cambridge University Press.
  2. [3]3. Bonacich P (1987) Power and centrality: a family of measures. American Journal of Sociology 92: 1170-1182.
  3. [5]5. Newman M (2010) Networks: An Introduction. Oxford University Press.
  4. [6]6. Easley D, Kleinberg J (2010) Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press.
  5. [7]7. Ahn YY, Han S, Kwak H, Moon S, Jeong H (2007) Analysis of topological characteristics of huge online social networking services. In: Proceedings of the 16th international conference on World Wide Web. ACM, pp. 835-844.
  6. [9]9. Mislove A, Koppula H, Gummadi K, Druschel P, Bhattacharjee B (2008) Growth of the Flickr social network. In: Proceedings of the first workshop on Online social networks. ACM, pp. 25-30.
  7. [14]14. Leskovec J, Horvitz E (2008) Planetary-scale views on a large instant-messaging network. In: Proceeding of the 17th international conference on World Wide Web. ACM, pp. 915-924.
  8. [15]15. Jiang J, Wilson C, Wang X, Huang P, Sha W, et al. (2010) Understanding latent interactions in online social networks. In: Proceedings of the 10th annual conference on Internet measurement. ACM, pp. 369-382.
  9. [16]16. Chang J, Rosenn I, Backstrom L, Marlow C (2010) ePluribus: ethnicity on social networks. In: Proceedings of the International conference in weblogs and social media.
  10. [17]17. Traud A, Kelsic E, Mucha P, Porter M (2008) Community structure in online collegiate social networks. Preprint arXiv:0809.0690v2 · arXiv
  11. [19]19. Traud A, Mucha P, Porter M (2011) Social structure of Facebook networks. Preprint arXiv:1102.2166. · arXiv
  12. [21]21. Viswanath B, Mislove A, Cha M, Gummadi K (2009) On the evolution of user interaction in Facebook. In: Proceedings of the 2nd workshop on Online social networks. ACM, pp. 37-42.
  13. [22]22. Catanese SA, De Meo P, Ferrara E, Fiumara G, Provetti A (2011) Crawling Facebook for social network analysis purposes. In: Proceedings of the international conference on Web intelligence, mining and semantics. ACM, pp. 52:1-52:8.
  14. [23]23. Gjoka M, Kurant M, Butts C, Markopoulou A (2010) Walking in Facebook: a case study of unbiased sampling of OSNs. In: Proceedings of International conference on computer communications. IEEE, pp. 1-9.
  15. [25]25. Clauset A, Shalizi CR, Newman MEJ (2009) Power-law distributions in empirical data. SIAM Review 51: 661-703.
  16. [28]28. Bollob´ as B (2001) Random Graphs. Cambridge University Press.
  17. [30]30. Feld S (1991) Why your friends have more friends than you do. American Journal of Sociology 96: 1464-1477.
  18. [31]31. Newman MEJ (2002) Assortative mixing in networks. Physical Review Letters 89: 208701.
  19. [32]32. Newman MEJ (2003) Mixing patterns in networks. Physical Review E 67: 026126.
  20. [33]33. Pastor-Satorras R, V´ azquez A, Vespignani A (2001) Dynamical and correlation properties of the internet. Physical Review Letters 87: 258701.
  21. [34]34. Zuckerman E, Jost J (2001) What makes you think you're so popular? Self-evaluation maintenance and the subjective side of the 'friendship paradox'. Social Psychology Quarterly : 207-223.
  22. [36]36. McPherson M, Smith-Lovin L, Cook JM (2001) Birds of a feather: homophily in social networks. Annual Review of Sociology 27: 415-444.
  23. [41]41. Liben-Nowell D, Novak J, Kumar R, Raghavan P, Tomkins A (2005) Geographic routing in social networks. Proceedings of the National Academy of Sciences USA. 33:11623-11628.
  24. [43]43. Backstrom L, Sun E, Marlow C (2010) Find me if you can: improving geographical prediction with social and spatial proximity. In: Proceedings of the 19th international conference on World Wide Web. ACM, pp. 61-70.
  25. [45]45. Thusoo A, Shao Z, Anthony S, Borthakur D, Jain N, et al. (2010) Data warehousing and analytics infrastructure at Facebook. In: Proceedings of the 2010 international conference on Management of data. ACM, pp. 1013-1020.
  26. [46]46. Thusoo A, Sarma J, Jain N, Shao Z, Chakka P, et al. (2010) Hive-a petabyte scale data warehouse using Hadoop. In: Proceedings of the 26th international conference on Data engineering. IEEE, pp. 996-1005.
  27. [47]47. Newman MEJ, Ziff RM (2001) Fast Monte Carlo algorithm for site or bond percolation. Physical Review E 64: 016706.
  28. [48]48. Boldi P, Rosa M, Vigna S (2011) HyperANF: approximating the neighbourhood function of very large graphs on a budget. In: Proceedings of the 20th international conference on World Wide Web. ACM, pp. 625-634. Table 1. ISO country codes used as labels in Figure 9.

Authors
Ugander, J., Karrer, B., Backstrom, L., & Marlow, C.
Affiliations
  • Cornell University (US)
  • University of Michigan (US)
  • Meta (United Kingdom) (GB)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2011
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1111.4503
arXiv
1111.4503
OpenAlex
W1893161742
Cited by
819
References
49
Citations by year
2026: 2 · 2025: 13 · 2024: 19 · 2023: 20 · 2022: 34 · 2021: 84 · 2020: 66 · 2019: 44 · 2018: 63 · 2017: 58 · 2016: 80 · 2015: 104 · 2014: 109 · 2013: 84 · 2012: 37
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
Keywords
social network structure, degree distribution, clustering coefficient, six degrees of separation, assortativity, friendship networks, community structure, gender homophily

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review