Optimization Online


Least cost influence propagation in (social) networks

Matteo Fischetti (matteo.fischetti***at***unipd.it)
Michael Kahr (m.kahr***at***univie.ac.at)
Markus Leitner (markus.leitner***at***univie.ac.at)
Michele Monaci (michele.monaci***at***unibo.it)
Mario Ruthmair (mario.ruthmair***at***univie.ac.at)

Abstract: Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept of activation functions is proposed together with strengthening inequalities. Exact and heuristic solution methods are developed and compared for the new problem. Our computational results also show that our approaches outperform the state-of-the-art on relevant, special cases of the GLCIP.

Keywords: Influence maximization, Mixed-integer programming, Social network analysis

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences

Category 3: Integer Programming

Citation: Mathematical Programming, to appear, 2018


Entry Submitted: 01/30/2018
Entry Accepted: 01/30/2018
Entry Last Modified: 05/07/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