Estimating Social Network Structures Under Extreme API Constraints

TL;DR

As Online Social Networks (OSNs) tighten privacy controls, researchers are losing access to basic node metadata like "degree" (friend counts). This paper explores whether we can still estimate the total size and average connectivity of a network if the only thing an API tells us is the ID of one random friend. The verdict: Average degree is surprisingly easy to find, but total network size remains an "extreme" challenge.

The "Black Box" Motivation

Traditional graph sampling (like Metropolis-Hastings) relies on knowing the degree of the current node to decide where to move next. However, OSN providers now often provide "Black Box" APIs. In this paper's Random Neighbor API (RNA) model, querying a user returns exactly one random neighbor ID.

The core insight is: Can we infer the global structure if we are blind to local connectivity? Existing SOTA methods fail here because they require $d_i$ (degree of node $i$) to unbias the sampling results.

Methodology: Designing Blind Estimators

1. Multiplicity-Based Size Estimation (MB-VCB)

Since we cannot see degrees, the authors pivot to Vertex Multiplicity. If a Random Walk visits a node many times, its multiplicity becomes a proxy for its degree (as high-degree nodes are visited more often in a Simple Random Walk).

• The Adjustment: They apply a "safety margin" to ignore consecutive nodes in a walk, treating them as roughly independent samples to satisfy the requirements of collusion-based estimators.

2. Average Degree via Collision Theory (GEN-AD)

To estimate the average degree without seeing $d_i$, the authors "probe" each sampled node. By making multiple RNA calls for the same node and counting how many times the same neighbor ID appears (collusions), they can statistically estimate that node's degree.

Note: The authors leverage the Hansen-Hurwitz framework but substitute unknown selection probabilities with estimated multiplicities.

Experimental Battleground

The authors tested their math on 5 real-world datasets, including Facebook-New Orleans and Enron email graphs.

Key Findings:

• The Size Wall: As seen in the figure above, the MB-VCB estimator (the one that works under RNA) consistently underestimates the network size until the sampling fraction $f$ exceeds 10. In OSN terms, you would need to perform a walk much longer than the network itself to get an accurate count.
• The Average Degree Success: Contrary to size estimation, the GEN-AD estimator performs remarkably well. Even with only 10 RNA calls per node ($\omega =10$), the average degree converges quickly even when only 20% of the network is explored.

Critical Insight & Conclusion

The study reveals a fundamental theoretical trade-off: Local metadata (degree) is the "fuel" for global size estimation. Without it, the "collisions" needed to estimate size happen too infrequently to be practical.

However, for researchers interested in network density (average degree), the RNA model is not a dealbreaker. By spending a small "budget" of API calls to estimate local degrees via collisions, one can retrieve highly accurate global averages. This work sets a baseline for what is possible when OSNs become "dark" and only provide the bare minimum of connectivity data.

Future Outlook: The next frontier is applying this to even more complex metrics like the clustering coefficient or identifying community boundaries using only these sparse, random probes.