Source-linked AI summary
Crawling Facebook for Social Network Analysis Purposes
Salvatore A. Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, Alessandro Provetti
TL;DR
The paper addresses how to collect and analyze large online-social-network graphs when complete Facebook data are inaccessible and difficult to process. It compares BFS and Uniform sampling with social-network-analysis tools, collecting anonymous undirected samples containing millions of connections. The study reports that sampled graph properties, including effective diameter and connected components, require interpretation because sampling can leave about 5% of nodes disconnected.
Problem
Complete Facebook data are inaccessible and difficult to mine, store, traverse, and analyze, motivating representative partial samples and attention to sampling bias.
Method
The study compares BFS and Uniform sampling to collect partial Facebook graphs, then analyzes them with social-network-analysis tools and graph measures.
Results
About 5% of nodes remain disconnected from the largest connected components in the Uniform dataset, while its effective diameter remains too high and may reflect the sample's small size.
Takeaways & Limitations
Facebook friendship data can be collected as anonymous unweighted, undirected graphs and examined through degree, centrality, scaling, and friendship-distribution measures.
Takeaways & Limitations
Facebook returns at most 400 friends per friend-list page, while browser-based extraction that avoids this limit has too much computational overhead for large-scale crawling.
Abstract
from arXiv · showhide
We describe our work in the collection and analysis of massive data describing the connections between participants to online social networks. Alternative approaches to social network data collection are defined and evaluated in practice, against the popular Facebook Web site. Thanks to our ad-hoc, privacy-compliant crawlers, two large samples, comprising millions of connections, have been collected; the data is anonymous and organized as an undirected graph. We describe a set of tools that we developed to analyze specific properties of such social-network graphs, i.e., among others, degree distribution, centrality measures, scaling laws and distribution of friendship.
1. INTRODUCTION
Online social networks have become massive, scientifically valuable structures, but studying them requires automated collection, analysis metrics, and representative sampling because complete graphs are difficult to process.
- Online social networks have rapidly acquired hundreds of millions of users and increasingly represent interconnected relationships.
- Facebook presents substantial optimization and robustness challenges because it handles an estimated 13 million transactions per second at peak.
- Social network analysis requires suitable metrics to identify and evaluate structural properties of complex online social networks.
- Complete Facebook-graph analysis is impractical because mining the entire graph requires substantial computational resources and data handling.A prior study estimated 44 terabytes of data for downloading and handling the whole graph.
- Researchers therefore use small but representative graph samples, although standard sampling methodologies can introduce partial bias.
2. RELATED WORK
Related work spans graph sampling and crawling, online-network characterization, and social-network analysis, while this paper extends an earlier smaller-scale study with detailed results.
- Research on online social networks covers data collection, network characterization, and online social-network analysis.
- Graph-sampling studies develop efficient algorithms for visiting large graphs while reducing sampling bias.
- This paper provides detailed results building on preliminary work that used a significantly smaller sample and a naive collection technique.
- Prior work includes parallel crawling of online social networks and Facebook-specific collection using a Python crawler on a 56-machine cluster.
- Network-characterization research examines properties such as degree distribution and clustering in smaller samples, while other work models large-network dynamics.
- Social-network-analysis studies model node positions, clusters, giant components, and comparisons between simulations and actual network data.
3. METHODOLOGY
The methodology compares BFS and Uniform sampling for partial Facebook-graph collection, then analyzes the resulting graphs with social-network-analysis tools while considering scalability and sampling bias.
- Facebook users and friendships are represented as nodes and edges in an unweighted, undirected graph.
- The study gathers comparable Facebook subgraphs using two sampling methodologies and evaluates their properties with social-network-analysis techniques.
- The analysis compares sampled-network measures with Facebook-provided statistics to assess the reliability of collected data.
- Breadth-first-search sampling: BFS begins from a seed node, visits discovered neighbors through a FIFO queue, and expands coverage as a wavefront.
- Breadth-first-search sampling: The BFS crawl stops after covering at least three friendship sub-levels or running for 240 hours, producing an incomplete graph visit.
- Breadth-first-search sampling: Although incomplete BFS can bias results toward high-degree nodes, the study reports no statistically significant bias in its BFS data and compares it with Uniform sampling.
- Uniform sampling: Uniform sampling uses randomly generated user IDs, retains existing users and their friend lists, and discards nonexistent IDs.
4. DATA COLLECTION
The data-collection workflow prepares and runs a crawler, repeatedly extracts friend lists, cleans and deduplicates raw data, and structures the result in GraphML.
- The collection process begins with preparation for crawler execution and then starts or resumes data extraction.
- During execution, the crawler cyclically extracts friend lists from the Facebook data source.
- Raw data are collected until extraction concludes or the process is stopped.
- The workflow cleans and de-duplicates the collected information before structuring it in GraphML format.
- Figure 1 presents this workflow as a state diagram of the data-mining process.
4.1 Privacy policies
Facebook operates as a black box because business incentives and privacy concerns discourage information sharing, while access is constrained by user settings and technical extraction barriers.
- Facebook and other social-network services are reluctant to share user and usage information because targeted advertising supports their revenue.
- By default, users can access private information only from friends, although friend-list pages are publicly accessible.
- Facebook's terms prohibit data mining, while asynchronous friend-list delivery prevents naive extraction techniques.
4.2 Sampling sessions of Facebook
The study uses Facebook crawlers with different queue strategies to collect comparable samples, while privacy settings, traffic controls, and prior sampling concerns constrain acquisition.
- BFS crawler: The BFS crawler authenticates with cookies, starts from one seed, enqueues discovered friends in FIFO order, and visits them for ten days.
- Uniform crawler: The Uniform crawler retains the BFS architecture but changes queue generation and management.
- Uniform crawler: Only about one existing user was matched per eight attempts because assigned 32-bit IDs span approximately 2^29 ≃5.37e9 possibilities.
- Uniform crawler: The Uniform procedure generated eight random queues of 2^16 ≃65.5K IDs and ran eight agents for ten days to match the 63.4K-user BFS sample.
- Limitations: Privacy settings can prevent anonymous access to friend lists, while Facebook truncates lists above 400 friends and alternative extraction incurs excessive overhead at scale.
4.3 Data cleaning
The collected Facebook graphs are cleaned by removing redundant edges, standardizing and anonymizing identifiers, checking consistency, and exporting selected subgraphs in GraphML.
- Hash functions remove duplicate and parallel edges in linear time O(n).
- All user IDs are converted to a common numerical format with a 48-bit hybrid additive-rotative hash that avoids 32-bit collisions and anonymizes the datasets.
- The researchers verified data integrity and consistency, then converted selected ego-networks to GraphML for further experimentation.
4.4 Datasets
The study compares BFS and Uniform Facebook samples of similar scale using network statistics, finding broadly connected graphs but sampling-dependent differences in diameter and connectivity.
- BFS dataset: 12.58 million edges connected 8.21 million users in the BFS sample, including 63.4 thousand complete 2.0-degree ego-networks.
- Uniform dataset: The Uniform sample was designed to match the BFS dataset using eight queues, each containing approximately 65.5K IDs.
- Uniform dataset: The Uniform graph's clustering coefficient was acceptable but smaller than BFS, while approximately 5% of nodes remained disconnected.
5. RESULTS
The results compare BFS and Uniform sampling across degree distribution, distances, clustering, connectivity, and spectral properties, revealing both sampling differences and methodological caveats. BFS produces more regular or compact graph characteristics in several analyses, while Uniform sampling can leave more nodes disconnected.
- Degree distribution: BFS overestimates the degree distribution at both ends of the curves, partly reflecting Facebook’s friend-list cache limit of 400.The comparison uses BFS and Uniform sampling, with the cache limitation explicitly affecting the observed distributions.
- Degree distribution: The CCDF degree distribution is used to compare BFS and Uniform sampling, extending the degree-distribution analysis.The CCDF is presented in Figure 3 after the degree distributions are shown in Figure 2.
- Diameter and hops: BFS converges faster to the asymptotic hop value because its sample has a more compact graph structure.The hop plot relates reachable node pairs to the number of hops; the interpretation remains subject to sampling effects on diameter.
- Clustering coefficient: BFS shows less violent fluctuations in average clustering coefficient as a function of node degree, while the two samples fluctuate within similar intervals.The authors attribute the smoother BFS behavior to its more systematic sampling approach.
- Connected component: The largest connected components cover 99.98% of the BFS graph and 94.96% of the UNI graph.The remaining disconnected nodes are interpreted differently across samples, and the reported BFS collisions involve only 0.02% of hashed edges without affecting sample quality.
- Eigenvector: BFS spectral curves show more regular behavior for singular values and right singular vectors across adjacency-matrix rank.The authors associate this regularity with the richness of the BFS sampling.
5.2 Privacy Settings
Restrictive Facebook privacy settings reduced the Uniform crawler’s acquired-user count below its statistical expectation, limiting anonymous friend-list access.
- 48.1K users were collected instead of the statistically expected 65.5K with the Uniform crawler.The expected count was 8 · 2^16 ≃65.5K users.
- The discrepancy between expected and actual acquired users was about 26.6%.
- Roughly one quarter of Facebook users restricted friend-list visits to their friendship network.These privacy policies prevented other users from visiting their friend lists anonymously.
6. CONCLUSIONS
The study collected and analyzed anonymous Facebook friendship samples using BFS and Uniform sampling, finding that both confirmed several previously reported network properties despite practical incompleteness.
- The study represented Facebook users as nodes and relationships as edges in an unweighted, undirected graph.
- BFS and Uniform sampling were used because incomplete BFS visits are known to introduce bias.
- Both incomplete samples confirmed results for degree distribution, diameter, clustering coefficient, and eigenvalues distribution.
- Future work includes parallel code to accelerate data extraction and evaluation of network metrics.