  Given a social network $G$ and an integer $k$, the influence maximization
(IM) problem asks for a seed set $S$ of $k$ nodes from $G$ to maximize the
expected number of nodes influenced via a propagation model. The majority of
the existing algorithms for the IM problem are developed only under the
non-adaptive setting, i.e., where all $k$ seed nodes are selected in one batch
without observing how they influence other users in real world. In this paper,
we study the adaptive IM problem where the $k$ seed nodes are selected in
batches of equal size $b$, such that the $i$-th batch is identified after the
actual influence results of the former $i-1$ batches are observed. In this
paper, we propose the first practical algorithm for the adaptive IM problem
that could provide the worst-case approximation guarantee of
$1-\mathrm{e}^{\rho_b(\varepsilon-1)}$, where $\rho_b=1-(1-1/b)^b$ and
$\varepsilon \in (0, 1)$ is a user-specified parameter. In particular, we
propose a general framework AdaptGreedy that could be instantiated by any
existing non-adaptive IM algorithms with expected approximation guarantee. Our
approach is based on a novel randomized policy that is applicable to the
general adaptive stochastic maximization problem, which may be of independent
interest. In addition, we propose a novel non-adaptive IM algorithm called EPIC
which not only provides strong expected approximation guarantee, but also
presents superior performance compared with the existing IM algorithms.
Meanwhile, we clarify some existing misunderstandings in recent work and shed
light on further study of the adaptive IM problem. We conduct experiments on
real social networks to evaluate our proposed algorithms comprehensively, and
the experimental results strongly corroborate the superiorities and
effectiveness of our approach.
