Seeding with Partial Network Data: Hardness and Guarantees

Wednesday, February 13, 2019 - 3:00pm to 3:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Amin Rahimian



Building and Room Number

LIDS Lounge


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.


Amin Rahimian is a postdoctoral associate at the MIT Institute for Data, Systems, and Society (IDSS). He received his MS in systems engineering and PhD in electrical and systems engineering from the University of Pennsylvania, and an AM in statistics from the Wharton School at UPenn. His research interests include network science, statistics, control and decision theory, with applications to social and economic networks.