Adaptive Influence Maximization: Adaptability via Nonadaptability
Hongmin W. Du, Yingfan L. Du, Zhao Zhang
INFORMS Journal on Computing · 2024 · Volume 36 · Issue 5
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 𝑂 ( 𝑛 2 ) O ( n 2 ) time and has performance ratio 1 − 1 / √ 𝑒 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. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This research is supported in part by the National Natural Science Foundation of China [Grant U20A2068].
Keywords
adaptive influence maximization, reverse sampling, approximation algorithm
Enable JavaScript for citation tools and additional paper interactions.