2021/10/25 by Binghui Peng, Peng, Binghui · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Social and Information Networks (cs.SI) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2110.12602
openalex publication_date 2021/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate a systematic study on dynamic influence maximization (DIM). In the DIM problem, one maintains a seed set S of at most k nodes in a dynamically involving social network, with the goal of maximizing the expected influence spread while minimizing the amortized updating cost. We consider two evolution models. In the incremental model, the social network gets enlarged over time and one only introduces new users and establishes new social links, we design an algorithm that achieves (1-1/e-ε)-approximation to the optimal solution and has k \cdotpoly(log n, ε-1) amortized running time, which matches the state-of-art offline algorithm with only poly-logarithmic overhead. In the fully dynamic model, users join in and leave, influence propagation gets strengthened or weakened in real time, we prove that under the Strong Exponential Time Hypothesis (SETH), no algorithm can achieve 2^-(log n)1-o(1)-approximation unless the amortized running time is n1-o(1). On the technical side, we exploit novel adaptive sampling approaches that reduce DIM to the dynamic MAX-k coverage problem, and design an efficient (1-1/e-ε)-approximation algorithm for it. Our lower bound leverages the recent developed distributed PCP framework.