Timezone: »

Correlation Robust Influence Maximization
Louis Chen · Divya Padmanabhan · Chee Chin Lim · Karthik Natarajan

Wed Dec 09 09:00 PM -- 11:00 PM (PST) @ Poster Session 4 #1241

We propose a distributionally robust model for the influence maximization problem. Unlike the classical independent cascade model of Kempe et al (2003), this model's diffusion process is adversarially adapted to the choice of seed set. So instead of optimizing under the assumption that all influence relationships in the network are independent, we seek a seed set whose expected influence under the worst correlation, i.e., the ``worst-case, expected influence", is maximized. We show that this worst-case influence can be efficiently computed, and though the optimization is NP-hard, a (1 - 1/e) approximation guarantee holds. We also analyze the structure to the adversary's choice of diffusion process, and contrast with established models. Beyond the key computational advantages, we also study the degree to which the independence assumption may be considered costly, and provide insights from numerical experiments comparing the adversarial and independent cascade model.

Author Information

Louis Chen (Naval Postgraduate School)
Divya Padmanabhan (Singapore University of Technology and Design)
Chee Chin Lim (Singapore University of Technology and Design)
Karthik Natarajan (Singapore University of Technology and Design)