  We initiate a systematic study on $\mathit{dynamic}$ $\mathit{influence}$
$\mathit{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 $\mathit{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 $\mathit{fully}$ $\mathit{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.
