Coarse-grained topology estimation via graph sampling
Published in ACM workshop on Workshop on online social networks, 2012
Abstract
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, we show how to efficiently estimate the category graph from a probability sample of nodes. We prove consistency of our estimators and evaluate their efficiency via simulation. We also apply our 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.
Recommended citation: Kurant, M., Gjoka, M., Wang, Y., Almquist, Z. W., Butts, C. T., & Markopoulou, A. (2012, August). Coarse-grained topology estimation via graph sampling. In Proceedings of the 2012 ACM workshop on Workshop on online social networks (pp. 25-30).
Download Paper