Coarse-Grained Topology Estimation Via Graph Sampling

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.