Optimization Online


Large-scale Influence Maximization via Maximal Covering Location

Evren GŁney(guneye***at***mef.edu.tr)
Markus Leitner(markus.leitner***at***univie.ac.at)
Mario Ruthmair(mario.ruthmair***at***univie.ac.at)
Markus Sinnl(markus.sinnl***at***univie.ac.at)

Abstract: 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.

Keywords: influence maximization, maximal covering location, stochastic optimization, Benders decomposition

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Stochastic Programming

Citation: University of Vienna, Austria, 12/2018

Download: [PDF]

Entry Submitted: 12/11/2018
Entry Accepted: 12/11/2018
Entry Last Modified: 12/11/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society