- Dean Eckles
- Hossein Esfandiari
- Elchanan Mossel
- M. Amin Rahimian
ACM Conference on Economics and Computation (2019), pp. 421-422
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.
We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work