Robust Influence Maximization
published: Sept. 25, 2016, recorded: August 2016, views: 1364
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !