2011

The Anatomy of the Facebook Social Graph

Ugander, Johan, Karrer, Brian, Backstrom, Lars et al.

Understand

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.

Built on

Sociometry 32: 425-443
Travers J, Milgram S (1969) An experimental study of the small world problem · 1969
Earlier work this paper cites.
American Journal of Sociology 92: 1170–1182
Bonacich P (1987) Power and centrality: a family of measures · 1987
Earlier work this paper cites.
American Journal of Sociology 96: 1464-1477
Feld S (1991) Why your friends have more friends than you do · 1991
Earlier work this paper cites.
Cambridge: Cambridge University Press
Wasserman S, Faust K (1994) Social Network Analysis · 1994
Earlier work this paper cites.
Random Structures and Algorithms 6: 161-179
Molloy M, Reed B (1995) A critical point for random graphs with a given degree sequence · 1995
Earlier work this paper cites.
Nature 393: 440-442
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks · 1998
Earlier work this paper cites.
Science 286: 509-512
Barabási AL, Albert R (1999) Emergence of scaling in random networks · 1999
Earlier work this paper cites.
Cambridge University Press
Bollobás B (2001) Random Graphs · 2001
Earlier work this paper cites.
Physical Review Letters 87: 258701
Pastor-Satorras R, Vázquez A, Vespignani A (2001) Dynamical and correlation properties of the internet · 2001
Earlier work this paper cites.
Social Psychology Quarterly : 207–223
Zuckerman E, Jost J (2001) What makes you think you’re so popular? Self-evaluation maintenance and the subjective side of the “friendship paradox” · 2001
Earlier work this paper cites.
Annual Review of Sociology 27: 415-444
McPherson M, Smith-Lovin L, Cook JM (2001) Birds of a feather: homophily in social networks · 2001
Earlier work this paper cites.
Physical Review E 64: 016706
Newman MEJ, Ziff RM (2001) Fast Monte Carlo algorithm for site or bond percolation · 2001
Earlier work this paper cites.
Physical Review Letters 89: 208701
Newman MEJ (2002) Assortative mixing in networks · 2002
Earlier work this paper cites.
Physical Review E 67: 026126
Newman MEJ (2003) Mixing patterns in networks · 2003
Earlier work this paper cites.
American Journal of Public Health 94: 89
Bearman P, Moody J (2004) Suicide and friendships among American adolescents · 2004
Earlier work this paper cites.
Physica A 333: 529-540
Maslov S, Sneppen K, Zaliznyak A (2004) Detection of topological patterns in complex networks: correlation profile of the internet · 2004
Earlier work this paper cites.

Similar

Physical Review E 69: 026113
Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks · 2004
Cited alongside, same era.
Proceedings of the National Academy of Sciences USA. 33:11623-11628
Liben-Nowell D, Novak J, Kumar R, Raghavan P, Tomkins A (2005) Geographic routing in social networks · 2005
Cited alongside, same era.
Science 311: 88
Kossinets G, Watts D (2006) Empirical analysis of an evolving social network · 2006
Cited alongside, same era.
Journal of Computer-Mediated Communication 13: 210–230
boyd dm, Ellison NB (2007) Social network sites: definition, history, and scholarship · 2007
Cited alongside, same era.
In: Proceedings of the 16th international conference on World Wide Web. ACM, pp. 835–844
Ahn YY, Han S, Kwak H, Moon S, Jeong H (2007) Analysis of topological characteristics of huge online social networking services · 2007
Cited alongside, same era.
In: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM, pp. 29–42
Mislove A, Marcon M, Gummadi K, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks · 2007
Cited alongside, same era.
Communities and Technologies 2007 : 41–66
Golder S, Wilkinson D, Huberman B (2007) Rhythms of social interaction: messaging within a massive online network · 2007
Cited alongside, same era.
In: Proceedings of the first workshop on Online social networks. ACM, pp. 25–30
Mislove A, Koppula H, Gummadi K, Druschel P, Bhattacharjee B (2008) Growth of the Flickr social network · 2008
Cited alongside, same era.
In: Proceeding of the 17th international conference on World Wide Web. ACM, pp. 915–924
Leskovec J, Horvitz E (2008) Planetary-scale views on a large instant-messaging network · 2008
Cited alongside, same era.
Preprint arxiv:0809.0690v2
Original
Traud A, Kelsic E, Mucha P, Porter M (2008) Community structure in online collegiate social networks · 2008
Cited alongside, same era.
Social Networks 30: 330–342
Lewis K, Kaufman J, Gonzalez M, Wimmer A, Christakis N (2008) Tastes, ties, and time: a new social network dataset using Facebook.com · 2008
Cited alongside, same era.
In: Proceedings of the 2nd workshop on Online social networks. ACM, pp. 37–42
Viswanath B, Mislove A, Cha M, Gummadi K (2009) On the evolution of user interaction in Facebook · 2009
Cited alongside, same era.

Then

In: Proceedings of the 19th international conference on World Wide Web. ACM, pp. 591–600
Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media? · 2010
Later among the works it cites.
Science 328: 1029
Eagle N, Macy M, Claxton R (2010) Network diversity and economic development · 2010
Later among the works it cites.
In: Proceedings of the 10th annual conference on Internet measurement. ACM, pp. 369–382
Jiang J, Wilson C, Wang X, Huang P, Sha W, et al. (2010) Understanding latent interactions in online social networks · 2010
Later among the works it cites.
In: Proceedings of the International conference in weblogs and social media
Chang J, Rosenn I, Backstrom L, Marlow C (2010) ePluribus: ethnicity on social networks · 2010
Later among the works it cites.
In: Proceedings of International conference on computer communications. IEEE, pp. 1–9
Gjoka M, Kurant M, Butts C, Markopoulou A (2010) Walking in Facebook: a case study of unbiased sampling of OSNs · 2010
Later among the works it cites.
Physics Reports 486: 75-174
Fortunato S (2010) Community detection in graphs · 2010
Later among the works it cites.
Physics Reports 499: 1-101
Barthélemy M (2010) Spatial networks · 2010
Later among the works it cites.
In: Proceedings of the 19th international conference on World Wide Web. ACM, pp. 61–70
Backstrom L, Sun E, Marlow C (2010) Find me if you can: improving geographical prediction with social and spatial proximity · 2010
Later among the works it cites.
In: Proceedings of the 2010 international conference on Management of data. ACM, pp. 1013–1020
Thusoo A, Shao Z, Anthony S, Borthakur D, Jain N, et al. (2010) Data warehousing and analytics infrastructure at Facebook · 2010
Later among the works it cites.
In: Proceedings of the 26th international conference on Data engineering. IEEE, pp. 996–1005
Thusoo A, Sarma J, Jain N, Shao Z, Chakka P, et al. (2010) Hive–a petabyte scale data warehouse using Hadoop · 2010
Later among the works it cites.
Preprint arxiv:1102.2166
Original
Traud A, Mucha P, Porter M (2011) Social structure of Facebook networks · 2011
Closest in time.
In: Proceedings of the international conference on Web intelligence, mining and semantics. ACM, pp. 52:1–52:8
Catanese SA, De Meo P, Ferrara E, Fiumara G, Provetti A (2011) Crawling Facebook for social network analysis purposes · 2011
Closest in time.
Experimental Algorithms : 364–375
Eppstein D, Strash D (2011) Listing all maximal cliques in large sparse real-world graphs · 2011
Closest in time.
Internet world statistics
Miniwatts Marketing Group · 2011
Closest in time.
In: Proceedings of the 20th international conference on World Wide Web. ACM, pp. 625–634
Boldi P, Rosa M, Vigna S (2011) HyperANF: approximating the neighbourhood function of very large graphs on a budget · 2011
Closest in time.
( in submission
Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2012) Four degrees of separation · 2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…