Adaptive Influence Maximization: Adaptability via Nonadaptability

Hongmin W. Du (), Yingfan L. Du () and Zhao Zhang ()
Additional contact information
Hongmin W. Du: Accounting and Information Systems Department, Rutgers University, Piscataway, New Jersey 08854
Yingfan L. Du: Department of Finance, University of Texas, Austin, Texas 78712
Zhao Zhang: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China

INFORMS Journal on Computing, 2024, vol. 36, issue 5, 1190-1200

Abstract: Adaptive influence maximization is an important research problem in computational social networks, which is also a typical problem in the study of adaptive processing of information and adaptive construction of objects. In this paper, we propose a new method that reduces the adaptive influence maximization problem into a nonadaptive one in a different social network, so that an adaptive optimization can be solved by those methods for nonadaptive optimization. In addition, we provide a new approximation algorithm for the submodular maximization problem with a knapsack constraint, which runs in O ( n 2 ) time and has performance ratio 1 − 1 / e , where n is the number of nodes in the network. The ratio is better than the best known previous one with the same running time.

Keywords: adaptive influence maximization; reverse sampling; approximation algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0267 (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:orijoc:v:36:y:2024:i:5:p:1190-1200

Access Statistics for this article

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