Seeding with Partial Network Data: Hardness and Guarantees

The spread of behavior over social networks depends on the contact structure among individuals, and seeding the most influential agents can substantially enhance the extent of the spread. While the choice of the best seed set, known as influence maximization, is a computationally hard problem, many computationally efficient algorithms have been proposed to approximate the optimal seed sets with provable guarantees. However, most of the previous work on influence maximization assumes the knowledge of the entire network graph. On the other hand, in practice, obtaining full knowledge of the network structure is very costly. Online social networks can have billions of edges and surveying a node for the entire list of her contacts can be impractical. 

In this work, we propose a ''probe-and-seed'' algorithm that provides almost tight approximation guarantees using \tilde O (sqrt(p) n^2) edge queries in \tilde O (sqrt(p) n^2) time, where n is the network size and p is the independent probability of spreading through an edge. To the best of our knowledge, this is the first result to provide approximation guarantees for influence maximization, using a sub-quadratic number of queries for polynomially small p. We complement this result by information theoretic arguments that show it is impossible to approximate the problem using o(n^2) queries regardless of p.