Dynamic Influence Maximization

Abstract

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-\epsilon )$-approximation to the optimal solution and has $k\cdot \mathsf{poly}(\log n,{\epsilon }^{-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 $n^{1-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-\epsilon )$-approximation algorithm for it. Our lower bound leverages the recent developed distributed PCP framework.

References in corpus (4)

• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
• On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback