Jump to Content

Seeding with Costly Network Information

Dean Eckles
Hossein Esfandiari
Elchanan Mossel
M. Amin Rahimian
ACM Conference on Economics and Computation (2019), pp. 421-422
Google Scholar

Abstract

Seeding the most influential individuals based on the contact structure can substantially enhance the extent of a spread over the social network. Most of the influence maximization literature assumes the knowledge of the entire network graph. However, in practice, obtaining full knowledge of the network structure is very costly. We propose polynomial-time algorithms that provide almost tight approximation guarantees using a bounded number of queries to the graph structure. We also provide impossibility results to lower bound the query complexity and show tightness of our guarantees.