计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 7-13.doi: 10.11896/jsjkx.200200071

所属专题: 理论计算机科学

• 理论计算机科学 • 上一篇    下一篇

在线影响力最大化研究综述

孔芳1, 李奇之2, 李帅3   

  1. 1 山东大学软件学院 济南250101
    2 西安电子科技大学计算机科学与技术学院 西安710071
    3 上海交通大学约翰·霍普克罗夫特计算机科学中心 上海201100
  • 收稿日期:2020-02-15 出版日期:2020-05-15 发布日期:2020-05-19
  • 通讯作者: 李帅(shuaili8@sjtu.edu.cn)
  • 作者简介:kongfang0801@foxmail.com

Survey on Online Influence Maximization

KONG Fang1, LI Qi-zhi2, LI Shuai3   

  1. 1 School of Software,Shandong University,Jinan 250101,China
    2 School of Computer Science and Technology,Xidian University,Xi'an 710071,China
    3 John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 201100,China
  • Received:2020-02-15 Online:2020-05-15 Published:2020-05-19
  • About author:KONG Fang,born in 1998,undergra-duate.Her main research interests include online influence maximization and so on.
    LI Shuai,born in 1988,Ph.D,assistant professor.Her main research interests include multi-armed bandit,online learning,statistical learning,reinforcement learning,machine learning and bioinformatics.

摘要: 影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。

关键词: 多臂老虎机, 社交网络, 影响力传播模型, 影响力最大化, 在线学习算法

Abstract: Influence maximization is selecting seed nodes under a given influence propagation model to maximize the information spread.This problem has a wide range of application scenarios,including recommendation systems,viral marketing,information diffusion and link prediction.In practical applications,the node-to-node propagation probabilities in an information propagation model are usually unknown.Besides,online learning algorithms can automatically learn unknown parameters during the interaction process and gradually approach the optimal solution.The paper first discusses the definition of influence maximization problem,introduces commonly used influence propagation models,and summarizes the common offline influence maximization algorithms.Then it introduces the classic online learning framework,the multi-armed bandit setting,analyzes the research status of online influence maximization problem,and compares the performance of common online influence maximization algorithms in real social networks through experiments.Finally,the challenges and research directions of this subject in the future is prospected.

Key words: Influence maximization, Influence propagation model, Multi-armed bandit, Online learning algorithm, Social network

中图分类号: 

  • TP391
[1]KEMPE D,KLEINBERG J M,TARDOS É.Maximizing thespread of influence through a social network[J].Theory of Computing,2015,11(4):105-147.
[2]CENTOLA D,MACY M.Complex contagion and the weakness of long ties[J].American Journal of Sociology,2007,113(3):702-734.
[3]WANG C,CHEN W,WANG Y.Scalable influence maximization for independent cascade model in large-scale social networks[J].Data Mining and Knowledge Discovery,2012,25(3):545-576.
[4]CHEN W,YUAN Y,ZHANG L.Scalable influence maximization in social networks under the linear threshold Model[C]//Proceedings of the 10th IEEE International Conference on Data Mining (ICDM).2010:88-97.
[5]CHEN W,LAKSHMANAN L V S,CASTILLO C.Information and Influence Propagation in Social Networks[M].Morgan & Claypool Publishers,2013.
[6]LESKOVEC J,KRAUSE A,GUESTIN C,et al.Cost-effective outbreakdetection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining (KDD).2007:420-429.
[7]GOYAL A,LU W,LAKSHMANAN L V S.CELF++: Optimizing the greedy algorithm for influence maximization in social networks (poster entry)[C]//Proceedings of the 20th International World Wide Web Conference (WWW).2011:47-48.
[8]KIMURA M,SAITO K,NAKANO R.Extracting influentialnodes for information diffusion on a social network[C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI).2007:1371-1376.
[9]CHEN W,WANG Y, YANG S.Efficient influence maximization in social networks[C]//Proceedings of the 15thACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2009:199-208.
[10]GOYAL A,LU W,LAKSHMANAN L V S.SIMPATH: An efficient algorithm for influence maximization under the linear threshold model[C]// Proceedings of the 11th IEEE International Conference on Data Mining (ICDM).2011:211-220.
[11]JUNG K,HEO W,CHEN W.IRIE: Scalable and robust influence maximization in social networks[C]//Proceedings of the 12th IEEE International Conference on Data Mining (ICDM).2012:918-923.
[12]KIM J,KIM S K,YU H.Scalable and parallelizable processing of influence maximization for large-scalesocial networks[C]//Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE).2013:266-277.
[13]WANG Y,CONG G,SONG G,et al.Community-based greedyalgorithm for mining top-K influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2010:1039-1048.
[14]JIANG Q,SONG G,CONG G,et al.Simulated annealing based influence maximization in social networks[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI).2011:127-132.
[15]BORGS C,BRAUTBAR M,CHAYES J,et al.Maximizing social influence in nearly optimal time[C]//Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA).2014:946-957.
[16]TANG Y,XIAO X,SHI Y.Influence maximization: near-optimal time complexity meets practical efficiency[C]//Proceedings of ACM SIGMOD Conference (SIGMOD).2014:75-86.
[17]TANG Y,SHI Y,XIAO X.Influence maximization in near-li-near time: A martingale approach[C]//Proceedings of ACM SIGMOD Conference (SIGMOD).2015:1539-1554.
[18]CHEN W.An issue in the martingale analysis of the influence maximization algorithm IMM[J].arXiv:1808.09363,2018.
[19]NGUYEN H T,THAI M T,DINH T N.Stop-and-Stare: Optimal sampling algorithms for viral marketing in billion- scale networks[C]// Proceedings of the 2016 International Conference on Management of Data (SIGMOD).2016:695-710.
[20]NGUYEN H T,NGUYEN T P,PHAN N H,et al.Importance sketching of influence dynamics in billion-scale networks[C]//Proceedings of the 2017 IEEE International Conference on Data Mining (ICDM).2017.
[21]AUDIBERT J-Y,BUBECK S,LUGOSI G.Minimax policies for combinatorial prediction games[C]//Proceedings of the 24th Annual Conference on Learning Theory (COLT).2011.
[22]LEI S,MANIU S,MO L,et al.Online influence maximization[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2015:645-654.
[23]CHEN W,WANG Y,YUAN Y,et al.Combinatorial multi-armed bandit and its extension toprobabilistically triggered arms[J].Journal of Machine Learning Research,2016,17(50):1-33.
[24]AUER P,CESA-BIANCHI N,FISCHER P.Finite-time analysis of the multiarmed bandit problem[J].Machine Learning Journal,2002,47(2/3):235-256.
[25]WANG Q,CHEN W.Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications[C]//Proceedings of the 30 th Annual Conference on Neural Information Processing Systems (NeurIPS).2017.
[26]WEN Z,KVETON B,VALKO M,et al.Online influence maximization under independent cascade modelwith semi-bandit feedback[C]//Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NeurIPS).2017.
[27]WU Q Y,LI Z G,WANG H Z,et al.Factorization Bandits for Online Influence Maximization[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining (KDD).2019: 636-646.
[28]VASWANI S,LAKSHMANAN L V S,SCHMIDT M.Influence maximization with bandits[C]//NIPS Workshop on Networks in the Social and Information Sciences.2015.
[29]BAO Y X,WANG X K,WANG Z,et al,Online influence maximization in non-stationary social networks[C]//IEEE/ACM 24th International Symposium on Quality of Service (IWQoS).2016.
[30]VASWANI S,KVETON B,WEN Z,et al.Diffusion independent semi-bandit influence maximization[C]//Proceedings of the 34 th International Conference on Machine Learning (ICML).2017.
[31]CARPENTIER A,VALKO M.Revealing graph bandits formaximizing local influence[C]//International Conference on Artificial Intelligence and Statistics.2016.
[32]LUGOSI G,NEU G,OLKHOVSKAYA J.Online influencemaximization with local observations[C]// Proceedings of the 30th International Conference on Algorithmic Learning Theory.2019:557-580.
[33]AUER P,CESA-BIANCHI N,FREUND Y,et al.The non-stochastic multi-armed bandit problem[J].SIAM Journal on Computing,2002,32(1):48-77.
[34]LINT,LI J,CHEN W,Stochastic Online Greedy Learning with Semi-bandit Feedbacks[C]//Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NeurIPS).2015:352-360.
[35]LICHAO S,WEIRAN H,PHILIP S Y,et al.Multi-Round Influence Maximization[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).2018: 2249-2258.
[1] 孔世明, 冯永, 张嘉云.
融合知识图谱的多层次传承影响力计算与泛化研究
Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph
计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144
[2] 王剑, 彭雨琦, 赵宇斐, 杨健.
基于深度学习的社交网络舆情信息抽取方法综述
Survey of Social Network Public Opinion Information Extraction Based on Deep Learning
计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099
[3] 魏鹏, 马玉亮, 袁野, 吴安彪.
用户行为驱动的时序影响力最大化问题研究
Study on Temporal Influence Maximization Driven by User Behavior
计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145
[4] 余皑欣, 冯秀芳, 孙静宇.
结合物品相似性的社交信任推荐算法
Social Trust Recommendation Algorithm Combining Item Similarity
计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217
[5] 畅雅雯, 杨波, 高玥琳, 黄靖云.
基于SEIR的微信公众号信息传播建模与分析
Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR
计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169
[6] 左园林, 龚月姣, 陈伟能.
成本受限条件下的社交网络影响最大化方法
Budget-aware Influence Maximization in Social Networks
计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228
[7] 郭磊, 马廷淮.
基于好友亲密度的用户匹配
Friend Closeness Based User Matching
计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[8] 王剑, 王玉翠, 黄梦杰.
社交网络中的虚假信息:定义、检测及控制
False Information in Social Networks:Definition,Detection and Control
计算机科学, 2021, 48(8): 263-277. https://doi.org/10.11896/jsjkx.210300053
[9] 谭琪, 张凤荔, 王婷, 王瑞锦, 周世杰.
融入结构度中心性的社交网络用户影响力评估算法
Social Network User Influence Evaluation Algorithm Integrating Structure Centrality
计算机科学, 2021, 48(7): 124-129. https://doi.org/10.11896/jsjkx.200600096
[10] 张人之, 朱焱.
基于主动学习的社交网络恶意用户检测方法
Malicious User Detection Method for Social Network Based on Active Learning
计算机科学, 2021, 48(6): 332-337. https://doi.org/10.11896/jsjkx.200700151
[11] 鲍志强, 陈卫东.
基于最大后验估计的谣言源定位器
Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation
计算机科学, 2021, 48(4): 243-248. https://doi.org/10.11896/jsjkx.200400053
[12] 张少杰, 鹿旭东, 郭伟, 王世鹏, 何伟.
供需匹配中的非诚信行为预防
Prevention of Dishonest Behavior in Supply-Demand Matching
计算机科学, 2021, 48(4): 303-308. https://doi.org/10.11896/jsjkx.200900090
[13] 袁得嵛, 陈世聪, 高见, 王小娟.
基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法
Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game
计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079
[14] 谭琪, 张凤荔, 张志扬, 陈学勤.
社交网络用户影响力的建模方法
Modeling Methods of Social Network User Influence
计算机科学, 2021, 48(2): 76-86. https://doi.org/10.11896/jsjkx.191200102
[15] 郁友琴, 李弼程.
基于多粒度文本特征表示的微博用户兴趣识别
Microblog User Interest Recognition Based on Multi-granularity Text Feature Representation
计算机科学, 2021, 48(12): 219-225. https://doi.org/10.11896/jsjkx.201100128
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!