Robustness to Dependency in Influence Maximization

• 成果类型: Article
• 署名作者: Chen, Louis L.; Lim, Chee Chin; Padmanabhan, Divya; Natarajan, Karthik
• 署名单位: United States Department of Defense; United States Navy; Naval Postgraduate School; National University of Singapore; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) Goa; Singapore University of Technology & Design
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2021.03445
• 发表日期: 2025
• 关键词: NETWORKS; graphs; programming; LINEAR; integer

摘要

In this paper, we pursue a correlation-robust study of the influence maximization problem. Departing from the classic independent cascade model, we study a diffusion process adversarially adapted to the choice of seed set. More precisely, rather than the independent 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 find that the worst case expected influence can be efficiently computed, its NP-hard optimization done approximately (1- 1/e) with greedy construction, and we provide complete, efficient characterizations of the adversarial coupling, the random graph, and the random number of influenced nodes. But, most importantly, upon mixing the independent cascade with the worst case, we attain a tunable and more comprehensive model better suited for real-world diffusion phenomena than the independent cascade alone and without increased computational complexity. Extensions to the correlationrobust study of risk follow along with numerical experiments on network data sets with demonstration of how our models can be tuned.