Least cost influence propagation in (social) networks

• 成果类型: Article; Proceedings Paper
• 署名作者: Fischetti, Matteo; Kahr, Michael; Leitner, Markus; Monaci, Michele; Ruthmair, Mario
• 署名单位: University of Padua; University of Vienna; University of Bologna
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1288-y
• 发表日期: 2018
• 页码: 293-325
• 关键词: dynamics

摘要

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.