  Networked representations of real-world phenomena are often partially
observed, which lead to incomplete networks. Analysis of such incomplete
networks can lead to skewed results. We examine the following problem: given an
incomplete network, which $b$ nodes should be probed to bring the largest
number of new nodes into the observed network? Many graph-mining tasks require
having observed a considerable amount of the network. Examples include
community discovery, belief propagation, influence maximization, etc. For
instance, consider someone who has observed a portion (say 1%) of the Twitter
retweet network via random tweet sampling. She wants to estimate the size of
the largest connected component of the fully observed retweet network. To
improve her estimate, how should she use her limited budget to reduce the
incompleteness of the network? In this work, we propose a novel algorithm,
called MaxOutProbe, which uses a budget $b$ (on nodes probed) to increase the
size of the observed network in terms of the number of nodes. Our experiments,
across a range of datasets and conditions, demonstrate the advantages of
MaxOutProbe over existing methods.
