TY - JOUR
T1 - Large-scale influence maximization via maximal covering location
AU - Güney, Evren
AU - Leitner, Markus
AU - Ruthmair, Mario
AU - Sinnl, Markus
PY - 2021/2/16
Y1 - 2021/2/16
N2 - 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. We introduce preprocessing tests, which allow us to remove variables from the model and develop efficient algorithms for the separation of Benders cuts. Both aspects are shown to be crucial ingredients of the developed branch-and-cut algorithm since real-life social network instances may be very large. In a computational study, the considered variants of this branch-and-cut algorithm outperform the state-of-the-art approach for influence maximization by orders of magnitude.
AB - 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. We introduce preprocessing tests, which allow us to remove variables from the model and develop efficient algorithms for the separation of Benders cuts. Both aspects are shown to be crucial ingredients of the developed branch-and-cut algorithm since real-life social network instances may be very large. In a computational study, the considered variants of this branch-and-cut algorithm outperform the state-of-the-art approach for influence maximization by orders of magnitude.
KW - Influence maximization
KW - Integer programming
KW - Large scale optimization
KW - Networks
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=85087780570&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087780570&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2020.06.028
DO - 10.1016/j.ejor.2020.06.028
M3 - Article
AN - SCOPUS:85087780570
VL - 289
SP - 144
EP - 164
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -