MaxReach: Reducing Network Incompleteness through Node Probes

S. Soundarajan, T. EliassiRad, B. Gallagher, A. Pinar
Proceedings of the 2016 IEEE/ACM ASONAM
San Francisco, CA, August 2016.
November 26, 2016

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.