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 worse-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.

该论文提出了鲁棒性影响最大化问题，通过参数不确定性建立最坏情况下影响扩散率与最优解之间的最大比率。其通过解决方案相关的方法设计了一种算法来解决这个问题，并进一步研究了均匀采样和自适应采样方法来提高影响最大化任务的鲁棒性。实验结果显示，参数不确定性可能会严重影响影响最大化的性能，并且基于信息级联的自适应采样方法可能是提高鲁棒性的有效方法。

稳健影响力最大化