Coarse-Grained Topology Estimation Via Graph Sampling

Download Now Free registration required

Executive Summary

In many online networks, nodes are partitioned into categories (e.g., countries or universities in OSNs), which naturally defines a weighted category graph i.e., a coarse-grained version of the underlying network. In this paper, the authors show how to efficiently estimate the category graph from a probability sample of nodes. They prove consistency of their estimators and evaluate their efficiency via simulation. They also apply their methodology to a sample of Facebook users to obtain a number of category graphs, such as the college friendship graph and the country friendship graph. They share and visualize the resulting data.

  • Format: PDF
  • Size: 662.7 KB