Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based on Benders decomposition is proposed and a relation between obtained Benders optimality cuts and submodular cuts for correspondingly defined subsets is established. In a computational study our branch-and-cut approaches outperform the state-of-the-art approaches for influence maximization by orders of magnitude.
Citation
University of Vienna, Austria, 12/2018