  In this paper, we address the important issue of uncertainty in the edge
influence probability estimates for the well studied influence maximization
problem --- the task of finding $k$ seed nodes in a social network to maximize
the influence spread. We propose the problem of robust influence maximization,
which maximizes the worst-case ratio between the influence spread of the chosen
seed set and the optimal seed set, given the uncertainty of the parameter
input. We design an algorithm that solves this problem with a
solution-dependent bound. We further study uniform sampling and adaptive
sampling methods to effectively reduce the uncertainty on parameters and
improve the robustness of the influence maximization task. Our empirical
results show that parameter uncertainty may greatly affect influence
maximization performance and prior studies that learned influence probabilities
could lead to poor performance in robust influence maximization due to
relatively large uncertainty in parameter estimates, and information cascade
based adaptive sampling method may be an effective way to improve the
robustness of influence maximization.
