# Dynamic Influence Maximization

arXiv: https://arxiv.org/abs/2110.12602 · HTML: https://mlsanity.com/paper/2110.12602/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2021.

## Built on by (most cited first, 6 of 6)

- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [Linear Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2407.02601/) (2024)
- [Influence Maximization (IM) in Complex Networks with Limited Visibility Using Statistical Methods](https://mlsanity.com/paper/2208.13166/) (2022)
- [Influence Maximization in Temporal Social Networks with a Cold-Start Problem: A Supervised Approach](https://mlsanity.com/paper/2504.11245/) (2025)

## Abstract (arXiv)

We initiate a systematic study on mathitdynamic mathitinfluence mathitmaximization (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 mathitincremental 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 ·mathsfpoly(log n, ε-1) amortized running time, which matches the state-of-art offline algorithm with only poly-logarithmic overhead. In the mathitfully mathitdynamic 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.