Least cost influence propagation in (social) networks

Matteo Fischetti, Michael Kahr, M. Leitner, Michele Monaci, Mario Ruthmair

Research output: Contribution to JournalArticleAcademicpeer-review


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.
Original languageEnglish
Pages (from-to)293-325
Number of pages33
JournalMathematical Programming
Issue number1
Early online date12 May 2018
Publication statusPublished - Jul 2018


Supported by WWTF (Project ICT15-014) and MiUR, Italy (Project PRIN 2015).

FundersFunder number
Vienna Science and Technology FundICT15-014
Ministero dell’Istruzione, dell’Università e della Ricerca


    • Influence Maximization
    • Mixed-Integer Programming
    • Social Network Analysis


    Dive into the research topics of 'Least cost influence propagation in (social) networks'. Together they form a unique fingerprint.

    Cite this