Large-scale influence maximization via maximal covering location

次模集函数 最大化 数学优化 概率逻辑 集合(抽象数据类型) 计算机科学 预处理器 钥匙(锁) 关系(数据库) 数学 算法 人工智能 数据挖掘 计算机安全 程序设计语言
作者
Evren Güney,Markus Leitner,Mario Ruthmair,Markus Sinnl
出处
期刊:European Journal of Operational Research [Elsevier]
卷期号:289 (1): 144-164 被引量:23
标识
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.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
淡淡清香完成签到 ,获得积分10
刚刚
今天是颗大白菜完成签到,获得积分10
1秒前
柳绿柳发布了新的文献求助10
5秒前
5秒前
6秒前
sdfdzhang完成签到 ,获得积分10
7秒前
干嘛鸭完成签到 ,获得积分10
9秒前
Ricky发布了新的文献求助10
11秒前
皮皮虾完成签到,获得积分10
12秒前
Russell完成签到 ,获得积分10
13秒前
nusiew完成签到,获得积分10
14秒前
mailgo完成签到,获得积分10
16秒前
Ricky完成签到,获得积分10
19秒前
我就想看看文献完成签到 ,获得积分10
19秒前
海丽完成签到 ,获得积分10
21秒前
zenabia完成签到 ,获得积分10
22秒前
yihuifa完成签到 ,获得积分10
25秒前
不安的晓灵完成签到 ,获得积分10
30秒前
尹沐完成签到 ,获得积分10
31秒前
自然亦竹完成签到,获得积分10
31秒前
等待香寒完成签到 ,获得积分10
32秒前
courage完成签到 ,获得积分10
34秒前
乐乐应助黑球采纳,获得10
36秒前
Jasper应助阳光的傲儿采纳,获得10
37秒前
刘秀完成签到 ,获得积分10
40秒前
王一生完成签到,获得积分10
43秒前
伯爵完成签到 ,获得积分10
46秒前
48秒前
50秒前
缓慢的绿草完成签到,获得积分10
50秒前
51秒前
元神完成签到 ,获得积分10
52秒前
53秒前
FashionBoy应助甜甜晓露采纳,获得10
59秒前
忆韶完成签到,获得积分10
59秒前
圆圆酱完成签到 ,获得积分10
1分钟前
小不完成签到 ,获得积分10
1分钟前
wp4455777完成签到,获得积分10
1分钟前
思源应助科研通管家采纳,获得10
1分钟前
薰硝壤应助科研通管家采纳,获得10
1分钟前
高分求助中
좌파는 어떻게 좌파가 됐나:한국 급진노동운동의 형성과 궤적 2500
Sustainability in Tides Chemistry 1500
TM 5-855-1(Fundamentals of protective design for conventional weapons) 1000
Cognitive linguistics critical concepts in linguistics 800
Threaded Harmony: A Sustainable Approach to Fashion 799
Livre et militantisme : La Cité éditeur 1958-1967 500
氟盐冷却高温堆非能动余热排出性能及安全分析研究 500
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 催化作用 物理化学 免疫学 量子力学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 3052652
求助须知:如何正确求助?哪些是违规求助? 2709891
关于积分的说明 7418319
捐赠科研通 2354494
什么是DOI,文献DOI怎么找? 1246122
科研通“疑难数据库(出版商)”最低求助积分说明 605951
版权声明 595921