MaxReach: Reducing network incompleteness through node probes

Sucheta Soundarajan, Tina Eliassi-Rad, Brian Gallagher, Ali Pinar

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

9 Scopus citations

Abstract

Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1%) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages152-157
Number of pages6
ISBN (Electronic)9781509028467
DOIs
StatePublished - Nov 21 2016
Event2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States
Duration: Aug 18 2016Aug 21 2016

Other

Other2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
CountryUnited States
CitySan Francisco
Period8/18/168/21/16

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Sociology and Political Science
  • Communication

Fingerprint Dive into the research topics of 'MaxReach: Reducing network incompleteness through node probes'. Together they form a unique fingerprint.

  • Cite this

    Soundarajan, S., Eliassi-Rad, T., Gallagher, B., & Pinar, A. (2016). MaxReach: Reducing network incompleteness through node probes. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 (pp. 152-157). [7752227] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASONAM.2016.7752227