Robust Influence Maximization
Wei Chen, Microsoft Research; Tian Lin*, Tsinghua University; Zihan Tan, IIIS, Tsinghua University; Mingfei Zhao, IIIS, Tsinghua University; Xuren Zhou, The Hong Kong University of Science and Technology
In this paper, we address the important issue of uncertainty in the edge inﬂuence probability estimates for the well studied inﬂuence maximization problem — the task of ﬁnding k seed nodes in a social network to maximize the inﬂuence spread. We propose the problem of robust inﬂuence maximization, which maximizes the worst-case ratio between the inﬂuence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We de-sign an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to eﬀectively reduce the uncertainty on parameters and improve the robustness of the inﬂuence maximization task. Our empirical results show that parameter uncertainty may greatly aﬀect inﬂuence maximization performance and prior studies that learned inﬂuence probabilities could lead to poor performance in robust inﬂuence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an eﬀective way to improve the robustness of inﬂuence maximization.