Robustness to Dependency in Influence Maximization

Louis L. Chen (), Chee Chin Lim (), Divya Padmanabhan () and Karthik Natarajan ()
Additional contact information
Louis L. Chen: Operations Research Department, Naval Postgraduate School, Monterey, California 93943
Chee Chin Lim: Institute of Operations Research and Analytics, National University of Singapore, Singapore 117602
Divya Padmanabhan: School of Mathematics and Computer Science at Indian Institute of Technology, Ponda, Goa 403401, India
Karthik Natarajan: Engineering Systems and Design, Singapore University of Technology and Design, Singapore 487372

Management Science, 2025, vol. 71, issue 3, 2696-2713

Abstract: 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 correlation-robust study of risk follow along with numerical experiments on network data sets with demonstration of how our models can be tuned.

Keywords: networks; graphs; programming; linear; integer (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2021.03445 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:71:y:2025:i:3:p:2696-2713

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().