Estimating Social Network Sizes: Why Biased Sampling is Your Best Friend

TL;DR

Estimating the size of massive social networks like Facebook via public APIs is a "black box" challenge. Traditional methods struggle because they demand uniform samples. This paper proves that biased sampling—sampling "popular" nodes more often via random walks—actually makes the estimation much faster, reducing the required samples from $O(\sqrt{n})$ to $O(n^{1/4})$.

Motivation: The Uniform Sampling Trap

In the world of graph theory and OSNs, we often want to know "How big is this network?" without having backend access. The standard statistical tool is Mark-and-Recapture (the "Birthday Paradox" logic): if you pick two random users and they happen to be the same person, you can starts to guess the total population.

However, there is a catch: this requires uniform sampling. To get a uniform sample from an API that only lets you see a user’s friends, you usually have to use "Rejection Sampling" (discarding many samples) or complex walks that converge slowly. In large-scale networks, this is prohibitively expensive in terms of API calls and time.

The Insight: Lean into the Bias

The authors ask: What if we don't try to be fair? A simple random walk on a graph (moving from friend to friend) naturally drifts toward "hubs"—users with many friends. Mathematically, the probability of hitting a node $v_i$ is proportional to its degree $d_i$. This is the stationary distribution.

Instead of fighting this bias, the authors use it. They track three specific metrics during a random walk:

1. $C$ (Collisions): Pairs of identical users sampled.
2. ${\Psi }_1$ (Sum of Degrees): Total friend counts of all sampled users.
3. ${\Psi }_{-1}$ (Sum of Reciprocals): Total of $1/d_{x_i}$ for sampled users.

The Core Formula

By combining these, they derive a simple, elegant estimator: $\hat{n}=\frac{{\Psi }_1{\Psi }_{-1}}{2C}$

This formula works because it compensates for the fact that high-degree nodes are more likely to collide.

Why It Works: The Zipfian Advantage

Social networks aren't random; they follow power-law distributions (Zipfian). In these networks, a few "celebrity" nodes have massive degrees. The paper shows that on such graphs, collisions happen much faster in a biased walk than in a uniform one. This "acceleration" allows the algorithm to converge with only $O(n^{1/4}\log n)$ samples. For a network of a billion nodes, this is the difference between needing 30,000 samples and just 6,000.

Experimental Results

The authors tested their algorithms on synthetic data and real-world datasets including DBLP and IMDB.

• Accuracy: On the IMDB network, the degree-biased sampling achieved a 10% error margin with 3x fewer samples than uniform methods.
• The "Facebook" Test: The team analyzed Facebook crawls from 2009 and 2010. Their estimate of ~475 million users in Oct 2010 was remarkably close to Facebook's official "500 million active users" report, accounting for private profiles and inactive accounts.

Deep Insight: Subgraph Estimation

One of the most powerful features of this method is its ability to estimate the size of sub-populations (e.g., "How many Facebook users live in Hyderabad?"). The authors demonstrate that you can estimate a subgraph's size even more efficiently by first estimating the total graph size and then looking at the relative frequency of the sub-population in your samples.

Final Analysis

This work is a masterclass in turning a statistical "problem" (sampling bias) into a computational "solution."

• Takeaway: If you are dealing with a graph that has a heavy-tailed degree distribution, stop trying to sample uniformly. You are throwing away valuable information.
• Limitation: The method assumes the graph is "well-mixed" (that a random walk can reach most parts of the graph quickly). If a network is highly fragmented into isolated islands, any sampling method will struggle.

For engineers and data scientists looking to benchmark competitor platforms or understand network growth, this biased sampling approach remains a foundational, high-efficiency technique.