Robust influence maximization

• Main Authors: LOWALEKAR, Meghna, Pradeep VARAKANTHAM, Akshat KUMAR
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Influence maximization; Regret; Column Generation; Optimization; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3602; https://ink.library.smu.edu.sg/context/sis_research/article/4603/viewcontent/robust_influence_maximization.pdf
• Institution: Singapore Management University

Influence Maximization is the problem of finding a fixed size set of nodes, which will maximize the expected number of influenced nodes in a social network. The number of influenced nodes is dependent on the influence strength of edges that can be very noisy. The noise in the influence strengths can be modeled using a random noise or adversarial noise model. It has been shown that all random processes that independently affect edges of the graph can be absorbed into the activation probabilities themselves and hence random noise can be captured within the independent cascade model. On the other hand, similar to He et al., we consider the adversarial noise where influence strength for an edge can belong to any point in the interval: [pu,v, pu,v] and the exact values are chosen by an adversary from this interval. The problems of evaluating robustness of a given solution and computing robust optimal solutions have received scant attention in the literature and are of key interest in this paper. Specifically, we aim to minimize (over all available seed sets) the maximum (over all instantiations of influence strengths) regret. Concretely, the key contributions are: (1) We show that maximum regret for a given solution is attained when influence strength on each of the edges is set to one of the extreme values of the influence strength intervals on edges. (2) We provide a novel way of considering samples that accounts for the noise in influence strength on all edges. (3) We develop a framework which provides an approach to get an optimal regret solution and more importantly a metric to evaluate robustness of a given solution based on the regret optimal solution. (4) Finally, we show results on evaluating the robustness of the well known greedy approach. Surprisingly, even without considering noise in influence strengths explicitly, greedy approach achieves highly robust solutions on small-medium scale social network instances.