Title: Multi-Round Influence Maximization (Extended Version),
Abstract: In this paper, we study the Multi-Round Influence Maximization (MRIM)
problem, where influence propagates in multiple rounds independently from
possibly different seed sets, and the goal is to select seeds for each round to
maximize the expected number of nodes that are activated in at least one round.
MRIM problem models the viral marketing scenarios in which advertisers conduct
multiple rounds of viral marketing to promote one product. We consider two
different settings: 1) the non-adaptive MRIM, where the advertiser needs to
determine the seed sets for all rounds at the very beginning, and 2) the
adaptive MRIM, where the advertiser can select seed sets adaptively based on
the propagation results in the previous rounds. For the non-adaptive setting,
we design two algorithms that exhibit an interesting tradeoff between
efficiency and effectiveness: a cross-round greedy algorithm that selects seeds
at a global level and achieves $1/2 - \varepsilon$ approximation ratio, and a
within-round greedy algorithm that selects seeds round by round and achieves
$1-e^{-(1-1/e)}-\varepsilon \approx 0.46 - \varepsilon$ approximation ratio but
saves running time by a factor related to the number of rounds. For the
adaptive setting, we design an adaptive algorithm that guarantees
$1-e^{-(1-1/e)}-\varepsilon$ approximation to the adaptive optimal solution. In
all cases, we further design scalable algorithms based on the reverse influence
sampling approach and achieve near-linear running time. We conduct experiments
on several real-world networks and demonstrate that our algorithms are
effective for the MRIM task.