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


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.

Related publications