Source-linked AI summary
The Anatomy of the Facebook Social Graph
Johan Ugander, Brian Karrer, Lars Backstrom, Cameron Marlow
TL;DR
The paper asks what the structure of the largest analyzed online social network reveals about human relationships and graph analysis. It measures Facebook’s global structure, neighborhoods, and mixing patterns, finding near-full connectivity, short paths, dense local structure, and demographic assortativity. These results provide a large-scale empirical characterization while leaving further network-analysis possibilities open.
Problem
The paper addresses the need for large-scale, accurate empirical characterization of online social relationships and realistic graph representations.
Method
The authors analyze the entire active Facebook network with graph measures, connected-component calculations, and a degree-weighted definition of random neighbors.
Results
Average distance in the giant component was 4.7, while the network was nearly fully connected, locally dense, degree-assortative, age- and country-mixed, and globally modular.
Takeaways & Limitations
The study supplies a large-scale structural reference for social-network research and graph-analysis tools, including implications for graph traversal from dense, clustered neighborhoods.
Takeaways & Limitations
The analysis did not exhaust the possibilities of network analysis, and its active-user population was defined using a study-specific criterion rather than Facebook’s ordinary definition.
Abstract
from arXiv · showhide
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.
Introduction
The paper characterizes Facebook as a large-scale empirical representation of human social relationships, enabled by online-network data. It analyzes the entire active Facebook network to advance social-network knowledge and graph-analysis tools.
- Online social networks make previously hidden social structures observable at unprecedented scale and detail.
- Historical social-network studies were limited to hundreds of individuals, whereas online networks can map relationships at nearly global scale.
- 721 million active users comprised the Facebook network analyzed in May 2011, making it the largest social network analyzed to that point.
- Because online-network members are biased samples rather than controlled random samples, network completeness is especially important.
- Active users were defined as members who logged in within the previous 28 days and had at least one Facebook friend.
- The study aims both to advance knowledge of social networks and to support graph algorithms and network-analysis tools with an accurate relationship representation.
Results
This section introduces graph measurements of Facebook, including degree distributions for global and U.S. users. The authors emphasize measurement results while placing technical details in the Methods.
- The analysis applies a wide variety of graph measures to the enormous Facebook social network using extensive computational resources.
- Figure 1 compares the fraction of users with exactly k friends globally and in the U.S. population.
- The CCDF reports the fraction of users whose degree is k or greater.
The Facebook Graph
The Facebook graph is globally sparse in degree structure yet nearly connected, with short paths and dense local neighborhoods. Its degree distribution is highly skewed, while neighborhood cohesion and two-hop reach expand substantially with user degree.
- Degree distribution: The degree distribution is right-skewed and curved on a log-log scale, so strict power-law models are inappropriate for Facebook.The global median friend count was 99, and the observed distribution has high variance and a 5000-friend cutoff.
- Global structure: 4.7 was the average distance between Facebook users, with 92% of pairs within five hops and 99.6% within six.The corresponding U.S. averages were 4.3, 96%, and 99.7%.
- Global structure: 99.91% of active Facebook users belong to the largest connected component, making short paths applicable to nearly the entire network.The second-largest component contains just over 2,000 individuals.
- Local neighborhoods: 0.14 was the average local clustering coefficient for users with 100 friends, meaning 14% of their friend pairs were also friends.This was approximately five times the coefficient reported for same-sized MSN Messenger neighborhoods, while clustering declined with degree and dropped rapidly near 5000 friends.
- Local neighborhoods: 15 was the average neighborhood degeneracy for users with 100 friends, rising to 53 for users with 500 friends.At 500 friends, at least 54 friends each knew 53 others, indicating dense cores inside an otherwise sparse graph.
- Two-hop neighborhoods: 27,500 unique and 40,300 non-unique friends-of-friends were associated with a user having 100 friends.Unique friends-of-friends grew close to linearly with degree, while non-unique counts grew only moderately faster than linearly.
Discussion
The study provides a large-scale structural characterization of Facebook, covering global connectivity, neighborhood density, user assortativity, demographic mixing, and community organization. It also identifies open possibilities for further network analysis and applications to social science and graph algorithms.
- The study characterizes Facebook’s structure using many metrics and tools, presenting the largest structural analysis of a social network to date.
- Facebook exhibits a skewed friendship-count distribution with large variance, but a pure power-law is inappropriate despite the presence of hubs.
- 4.7 average distance between giant-component vertices confirms globally the small-world effect and six degrees of separation.
- Friends tend to have more friends, while highly clustered friendships create dense neighborhood cores with implications for graph traversal.
- Users show mixing by login behavior, age, and country, including same-age and same-country friendship preferences.
- Global community structure is evident between and within countries and is largely organized by geographical distance.
Materials and Methods
The analysis combines large-scale distributed computation with sampling and specialized algorithms to study neighborhoods, connected components, and path lengths.
- Calculations generally used a Hadoop cluster with 2,250 machines and the Hadoop/Hive data-analysis framework.
- 500,000 users were sampled by selecting 5,000 users for each of 100 log-spaced neighborhood sizes using reservoir sampling.
- The Newman-Zipf algorithm computed component structure dynamically as edges were added without retaining all edges in memory.
- Path lengths were estimated with HyperANF on a 24-core machine with 72 GB of RAM, averaging across 10 runs.