Coarse-grained topology estimation via graph sampling

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

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. We share and visualize the resulting data at www.geosocialmap.com.

Original languageEnglish (US)
Title of host publicationWOSN'12 - Proceedings of the ACM Workshop on Online Social Networks
Pages25-30
Number of pages6
DOIs
StatePublished - Sep 28 2012
Event2012 Workshop on Online Social Networks, WOSN 2012 Co-located with SIGCOMM 2012 - Helsinki, Finland
Duration: Aug 17 2012Aug 17 2012

Publication series

NameWOSN'12 - Proceedings of the ACM Workshop on Online Social Networks

Other

Other2012 Workshop on Online Social Networks, WOSN 2012 Co-located with SIGCOMM 2012
CountryFinland
CityHelsinki
Period8/17/128/17/12

Keywords

  • coarse-grained topology
  • estimators
  • facebook
  • induced subgraph sampling
  • online social networks
  • star sampling

Fingerprint Dive into the research topics of 'Coarse-grained topology estimation via graph sampling'. Together they form a unique fingerprint.

Cite this