Abstract
Estimating the global topology of massive online social networks (OSNs) is a significant challenge due to data access limitations. This paper presents a framework for estimating "coarse-grained" network structures by modeling them as Category Graphs. We introduce "star sampling," a method that leverages the categorical information of a node's entire neighborhood. Our results show that star sampling significantly outperforms traditional induced subgraph sampling, enabling accurate reconstruction of macro-scale connectivity—such as inter-country or inter-college friendship densities—with minimal data.
Introduction
Most research into large-scale Online Social Networks (OSNs) relies on sampling because downloading an entire graph is practically impossible. However, traditional sampling has a major blind spot: while it is effective at estimating local properties (like average degree), it struggles with global topology—the way different communities connect to one another.
To address this, we define the Category Graph $G^C$, where nodes represent groups (categories such as countries or workplaces) and edges represent the density of connections between them. The challenge lies in estimating these inter-group edge weights accurately without exhaustive crawling.
Sampling Methodologies
We propose two primary measurement strategies to estimate the category graph:
- Induced Subgraph Sampling: The standard approach where a set of nodes is sampled, and only the edges existing between those sampled nodes are observed.
- Star Sampling: Our key innovation. When a node is sampled, we observe the categories of all its neighbors (its "star"). Even if those neighbors are not in the primary sample, their categorical data provides significant information about inter-group connectivity.
These strategies are evaluated under both Uniform Independent Sampling (UIS) and Random Walks. While random walks are naturally biased toward high-degree nodes, we utilize Hansen-Hurwitz estimators to correct this bias. This turns a common sampling "bug" into a feature, as high-degree nodes provide more data per sample in the star sampling context.
Key Insights and Results
Our analysis reveals several critical advantages of the star sampling approach:
- Efficiency Gains: Star sampling is significantly more powerful than induced sampling, often requiring 5 to 10 times fewer samples to reach the same level of accuracy for inter-category edge weights.
- Convergence: All proposed estimators are mathematically proven to be consistent, converging to true values as sample size increases.
- Real-World Application: Using Facebook snapshots from 2009 and 2010, we successfully reconstructed "Geosocial Maps." These maps identified strong friendship cliques between specific geographic regions and demonstrated that physical distance remains a primary factor in digital connectivity, particularly for public institutions.
Conclusion and Future Work
Star sampling provides a robust framework for mapping the macro-scale structure of massive networks. While the current method assumes observable categories (like "Country" or "College"), future research will explore handling latent or hidden categories. Additionally, while the coarse-grained topology of large networks changes slowly, adapting these estimators for highly dynamic, rapidly growing networks remains an open area for study.
Summary updated