Correlation Robust Influence Maximization
This work addresses the problem of influence maximization in networks for researchers and practitioners by introducing a robust alternative to the independence assumption, though it is incremental as it builds on existing cascade models.
The authors tackled the influence maximization problem by proposing a distributionally robust model where the diffusion process is adversarially adapted to the seed set, maximizing worst-case expected influence instead of assuming independent relationships. They showed that worst-case influence can be efficiently computed, achieved a (1 - 1/e) approximation guarantee despite NP-hardness, and provided numerical insights comparing adversarial and independent cascade models.
We propose a distributionally robust model for the influence maximization problem. Unlike the classic independent cascade model \citep{kempe2003maximizing}, this model's diffusion process is adversarially adapted to the choice of seed set. Hence, 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 highlight the extent to which the independence assumption may cost optimality, and provide insights from numerical experiments comparing the adversarial and independent cascade model.