Decoding the Facebook Graph: A Comparative Study of BFS vs. Uniform Sampling

TL;DR

Understanding the structure of massive social networks is often hindered by the "walled gardens" of platforms like Facebook. This paper investigates how to bypass these barriers using custom-built crawlers. By comparing Breadth-First Search (BFS) and Uniform Sampling, the authors collected millions of anonymized connections to analyze the "small-world" nature of Facebook, finding that nearly 27% of users explicitly hide their social circles from the public.

Problem & Motivation

With over 500 million users (at the time of the study), Facebook represents a digital mirror of human society. However, extracting its graph is a monumental challenge for two reasons:

1. Scale: A full crawl would involve downloading tens of terabytes of data.
2. Accessibility: Facebook employs technical countermeasures (like asynchronous script loading) and behavioral policies to prevent automated mining.

Most researchers rely on sampling, but not all samples are created equal. The authors argue that we must understand the intrinsic bias of our tools before we can trust the metrics they produce.

Methodology: The Art of the Crawl

The researchers deployed two distinct strategies to capture a snapshot of the Facebook graph:

1. BFS Sampling (The Wavefront)

The BFS crawler starts at a "seed" node and visits friends in a FIFO queue. While efficient for discovering tightly-knit communities, it is known to gravitate toward "hubs"—users with a high number of connections—thereby skewing the results.

2. Uniform Sampling (The Unbiased Random)

By exploiting Facebook's 32-bit User-ID assignment system, the team generated random IDs and queried for their existence. This method is independent of the graph's structure, providing a more statistically sound view of the "average" user.

Figure 1: The state diagram of the data mining process, showing the cycle from crawler execution to GraphML structuring.

Structural Insights & Results

The study's results highlight the differences in how these algorithms "see" the network:

• Degree Distribution: Both samples confirmed a power-law distribution, but the BFS sample showed a noticeable overestimation in both the very low and very high degree ranges.
• The 400-Friend Ceiling: A key technical finding was Facebook's internal cache limit. The platform only returns a maximum of 400 friends per request, creating an artificial "peak" in the data at exactly 400.
• Connectivity: In the BFS sample, 99.98% of nodes belonged to the "Giant Component," whereas the Uniform sample (being truly random) had about 5% of its nodes disconnected from the main group.

Table 1: Comparing BFS and Uniform metrics. Note the discrepancy in average degree and the diameter.

Critical Analysis: Privacy and Bias

One of the most valuable insights of this paper is the quantitative analysis of Privacy Settings. By comparing the expected success rate of random ID hits against the actual successful extractions, the authors concluded that 26.6% of users have adjusted their privacy settings to block public access to their friend lists.

Limitations

• The Hard Ceiling: The 400-friend limit imposed by Facebook's backend means the "real" average degree is likely higher than reported.
• Temporal Snapshot: The study assumes a static graph during the 10-day crawl, though social networks are highly dynamic.

Conclusion

This work serves as a foundational blueprint for Online Social Network (OSN) research. It demonstrates that while BFS is faster for gathering massive amounts of connected data, Uniform Sampling is essential for validating structural properties without the bias of "hub-chasing." For future OSN researchers, the takeaway is clear: the architecture of your crawler dictates the "truth" of your data.