The Anatomy of the Facebook Social Graph

By Johan Ugander, Brian Karrer, Lars Backstrom, Cameron A. Marlow. arXiv.org, 2011

1,025 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

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

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 Statistical and Nonlinear Physics

Citations in the corpus

Investor Networks in the Stock Market (2014, neutral): “The median number of connections for an investor is 159, within the range of what is documented in the literature on social networks (e.g., Dunbar 1992; Hampton et al. 2011; Ugander et al. 2011).”
Embedding Logic Rules Into Recurrent Neural Networks (2019, background): “As shown in FIGURE 1, existing structured knowledge usually consists of a structured knowledge base [9], [10], social graph [11], and syntactic dependency [7].”
A Review of Facebook Research in the Social Sciences (2012, positive): “…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 Effect of Recommendations on Network Structure (2016, background): “(3)On the Facebook network, there is, somewhat surprisingly, a near-linear relationship between number of followers and number of followers-of-followers [28], perhaps because relationships are symmetric and users are limited to 5,000 connections.”
Differentially private data analysis of social networks via restricted sensitivity (2012, background): “Even in an anonymized unlabeled graph it is possible to identify people based on graph structures [3].”
Social Networks and Labor Markets: How Strong Ties Relate to Job Finding on Facebook’s Social Network (2017, background): “7% of users are connected by fewer than 6 degrees of separation (Ugander et al. 2011).”
Learning to Discover Social Circles in Ego Networks (2012, methodology): “We will then devise an unsupervised algorithm to jointly optimize the latent variables and the proﬁle similarity parameters so as to best explain the observed network data.”
Information network or social network?: the structure of the twitter follow graph (2014, background): “[14] found that the average clustering coefficient for degree = 5 is about 0.”
Rumor Cascades (2014, background): “2012; Granovetter 1973), people’s trust of information from their friends, and short path lengths (Ugander et al. 2011) together create an environment where information can spread quickly throughout the world.”
Digital Footprints: Opportunities and Challenges for Online Social Research (2014, methodology): “A similar analysis of the global Facebook network (Ugander et al. 2011) found that the number of steps separating users had declined from 5.3 in 2008 to 4.7 in 2011 as the network grew in size.”
Twitter as Data (2018, background): “, 2009; Gjoka, Irvine and Butts, 2010; Ferrara, 2012), physicists and computer scientists (Catanese et al., 2011; Ugander et al., 2011), social scientists (Lewis et al.”
The LDBC Social Network Benchmark: Interactive Workload (2015, background): “DATAGEN discretizes the power law distribution given by Facebook graph [14], but scales this according to the size of the network.”
Identifying Platform Effects in Social Media Data (2016, background): “…metrics of large online social networks differ from those of previously studied social networks (Corten 2012; Quercia, Capra, and Crowcroft 2012; Ugander et al. 2011; Mislove et al. 2007); we can continue to theorize how differences result from platform effects, usage patterns, and demographic…”
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.”
Knowledge Graphs: Opportunities and Challenges (2023, background): “• Facebook’s entity graph , a knowledge graph that converts the unstructured content of the user profiles into meaningful structured data (Ugander et al. 2011).”