Graser: Overcoming Structural Bias in Online Social Network Size Estimation

TL;DR

Estimating the size of modern Online Social Networks (OSNs) via Random Walks (RW) is notoriously unreliable when the network has many low-degree nodes. This paper presents Graser, an algorithm that uses subgraph sampling to "learn" the specific biases of a network's topology. By iteratively correcting collision counts, Graser slashes relative errors from a catastrophic 90% down to under 20% on platforms like LinkedIn.

Background: Why Counting Users is Hard

In an era of privacy restrictions and massive scale, we cannot simply "crawl" all of Facebook or LinkedIn. Researchers rely on Random Walk (RW) sampling—jumping from friend to friend—and using the "Capture-Recapture" logic (the Birthday Paradox) to estimate the total population based on how often the walker "collides" with a previously visited node.

Historically, this works well for balanced networks. However, the authors identify a critical failure mode: High Skewness. In networks like AMiner or LinkedIn, the walker gets "trapped" in clusters of low-degree nodes, causing excessive collisions and making the network appear much smaller than it actually is.

The "Structural Bias" Insight

The authors find that two mathematical metrics are the primary culprits for estimation failure:

1. Power-law parameter ($\alpha$): Higher values indicate a higher density of low-degree nodes.
2. Coefficient of Variation ($\gamma$): Lower dispersion around the mean degree correlates with higher collision errors.

Traditional estimators assume a standard stationary distribution that doesn't account for these local "traps."

Methodology: The Graser Framework

Graser's core innovation is a two-step iterative feedback loop:

1. EBFS Subgraph Construction

Instead of just sampling nodes, Graser uses Exploration by Breadth-First Search (EBFS) to build a tiny "mini-map" (subgraph) of the network. This subgraph preserves the degree distribution and rank-power-law properties of the original giant network.

Fig 1: The EBFS process ensures the subgraph is a structural mirror of the original OSN.

2. Iterative Calibration

Because we don't know the true sampling rate (since we don't know the total size), Graser:

• Performs an initial RW estimate.
• Estimates the current sampling rate.
• Runs a "simulated" RW on the subgraph to see how much the current topology biases the collision count.
• Uses that "error factor" to correct the global estimate.
• Repeats until the estimate stabilizes.

Experimental Results: A Massive Leap in Robustness

The performance gains are most visible in "difficult" networks. In the LinkedIn dataset (6.7M nodes), traditional RW estimators are effectively useless, with errors approaching 1.0 (100% error). Graser brings this down to a manageable 0.1-0.2 range.

Fig 2: Performance comparison across LinkedIn, AMiner, and Youtube datasets. Graser (colored lines) maintains low error while baseline methods (black lines) fail.

Key Takeaways from Ablation:

• Sampling Method Matters: Using Random Walk to build the subgraph (instead of EBFS) results in unstable, high-error estimates because RW oversamples high-degree nodes.
• Subgraph Size: As small as 3,000 to 5,000 nodes is enough to calibrate a network of millions.
• Efficiency: The extra time spent on subgraph sampling is negligible (~seconds) compared to the rate-limited API requests required for the actual network walk.

Conclusion & Future Look

Graser proves that the "instability" of network size estimation isn't a random occurrence but a predictable result of graph topology. By using subgraphs as calibration tools, we can finally achieve robust measurements of massive OSNs. Future work could potentially optimize the subgraph sampling to be even leaner, potentially enabling real-time monitoring of OSN growth rates.