Robustness to Dependency in Influence Maximization

In this paper, we introduce a correlation robust model for the influence maximization problem. Unlike the classic independent cascade model, this model’s diffusion process is adversarially adapted to the choice of seed set. More precisely, rather than only the in- dependent coupling of known individual edge probabilities, we now evaluate a seed set’s expected influence under all possible correlations - specifically, the one that presents the worst-case. We show that any seed set’s worst-case expected influence can be efficiently computed, and though optimizing the worst-case (over seed sets) is NP-hard, a (1 − 1/e) approximation algorithm can be obtained. We provide structural insights from the model and contrast it with the independent cascade model. We discuss how the proposed model can be extended to optimize other objectives by controlling for conservatism using a mix- ture of the independent and the worst-case distribution or by incorporating risk criterion in choosing the seed set. Finally we provide insights from numerical experiments to illustrate the usefulness of the model.

Download paper here

Louis Chen, Chee Chin Lim, Divya Padmanabhan, Karthik Natarajan (2024). “Robustness to Dependency in Influence Maximization.” accepted/forthcoming in Management Science.