TY - JOUR
T1 - Benders decomposition for competitive influence maximization in (social) networks
AU - Kahr, Michael
AU - Leitner, Markus
AU - Ruthmair, Mario
AU - Sinnl, Markus
PY - 2021/4
Y1 - 2021/4
N2 - Online social networks have become crucial to propagate information. Prominent use cases include marketing campaigns for products or political candidates in which maximizing the expected number of reached individuals is a common objective. The latter can be achieved by incentivizing an appropriately selected seed set of influencers that trigger an influence cascade with expected maximum impact. In real-world settings, competing influence spreads need to be considered frequently. These may, for instance, stem from marketing activities for a substitute product of a different company or bad actors that spread (mis-)information about a political candidate. This article focuses on competitive settings in which the seed individuals of one entity are already known. Another entity wants to choose its seed set of individuals that triggers an influence cascade of maximum impact. The propagation process is modeled by a variant of the probabilistic independent cascade model. An algorithmic framework based on a Benders decomposition is developed that also employs preprocessing and initial heuristics. This framework is used within a sample average approximation scheme that allows to approximate the exact objective function value. The algorithms are tested on real-world instances from the literature and newly-obtained ones from Twitter. A computational study reports on the algorithms’ performance next to providing further insights. The latter are based on analyzing expected losses that are caused by competition, the gain from solving subproblems to optimality using the Benders decomposition based algorithm, and the influence of different seed set choices of the first entity.
AB - Online social networks have become crucial to propagate information. Prominent use cases include marketing campaigns for products or political candidates in which maximizing the expected number of reached individuals is a common objective. The latter can be achieved by incentivizing an appropriately selected seed set of influencers that trigger an influence cascade with expected maximum impact. In real-world settings, competing influence spreads need to be considered frequently. These may, for instance, stem from marketing activities for a substitute product of a different company or bad actors that spread (mis-)information about a political candidate. This article focuses on competitive settings in which the seed individuals of one entity are already known. Another entity wants to choose its seed set of individuals that triggers an influence cascade of maximum impact. The propagation process is modeled by a variant of the probabilistic independent cascade model. An algorithmic framework based on a Benders decomposition is developed that also employs preprocessing and initial heuristics. This framework is used within a sample average approximation scheme that allows to approximate the exact objective function value. The algorithms are tested on real-world instances from the literature and newly-obtained ones from Twitter. A computational study reports on the algorithms’ performance next to providing further insights. The latter are based on analyzing expected losses that are caused by competition, the gain from solving subproblems to optimality using the Benders decomposition based algorithm, and the influence of different seed set choices of the first entity.
KW - Competitive influence maximization
KW - Social networks
KW - Integer linear programming
KW - Benders decomposition
UR - http://www.scopus.com/inward/record.url?scp=85084038338&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85084038338&partnerID=8YFLogxK
U2 - 10.1016/j.omega.2020.102264
DO - 10.1016/j.omega.2020.102264
M3 - Article
AN - SCOPUS:85084038338
SN - 0305-0483
VL - 100
SP - 1
EP - 13
JO - Omega
JF - Omega
M1 - 102264
ER -