Coarse-Grained Topology Estimation via Graph Sampling

Maciej Kurant, Minas Gjoka, Yan Wang, Zack W. Almquist, Carter T. Butts, Athina Markopoulou

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.

The transformation from an original graph $G$ to its corresponding category graph $G^C$, where edge weights represent connection densities between groups.

Sampling Methodologies

We propose two primary measurement strategies to estimate the category graph:

  1. Induced Subgraph Sampling: The standard approach where a set of nodes is sampled, and only the edges existing between those sampled nodes are observed.
  2. 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.
A comparison of (a) Induced subgraph sampling, which only sees edges between sampled nodes, and (b) Star sampling, which observes the categories of all neighbors of a sampled node.

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

BibTeX
@inproceedings{kurant2012coarse,
  author = {Maciej Kurant and Minas Gjoka and Yan Wang and Zack W. Almquist and Carter T. Butts and Athina Markopoulou},
  title = {{Coarse-Grained Topology Estimation via Graph Sampling}},
  booktitle = {WOSN},
  year = {2012},
  doi = {10.1145/2342549.2342556},
}
Figure