次模集函数
最大化
数学优化
概率逻辑
集合(抽象数据类型)
计算机科学
预处理器
钥匙(锁)
关系(数据库)
数学
算法
人工智能
数据挖掘
计算机安全
程序设计语言
作者
Evren Güney,Markus Leitner,Mario Ruthmair,Markus Sinnl
标识
DOI:10.1016/j.ejor.2020.06.028
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI