计算机科学 ›› 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 propagation model, Influence maximization, Social network, Online learning algorithm, Multi-armed bandit

中图分类号: 

  • 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] 马理博, 秦小麟. 话题-位置-类别感知的兴趣点推荐[J]. 计算机科学, 2020, 47(9): 81-87.
[2] 陈晋音, 张敦杰, 林翔, 徐晓东, 朱子凌. 基于影响力最大化策略的抑制虚假消息传播的方法[J]. 计算机科学, 2020, 47(6A): 17-23.
[3] 梁俊斌, 张敏, 蒋婵. 社交传感云安全研究进展[J]. 计算机科学, 2020, 47(6): 276-283.
[4] 刘晓飞, 朱斐, 伏玉琛, 刘全. 基于用户偏好特征挖掘的个性化推荐算法[J]. 计算机科学, 2020, 47(4): 50-53.
[5] 吴磊,岳峰,王含茹,王刚. 一种融合科研人员标签的学术论文推荐方法[J]. 计算机科学, 2020, 47(2): 51-57.
[6] 张敏军, 华庆一. 基于概率矩阵分解算法的社交网络用户兴趣点个性化推荐[J]. 计算机科学, 2020, 47(12): 144-148.
[7] 李霄, 曲阳, 李辉, 郭世凯. 基于用户关系的在线问答平台用户重要性评估方法[J]. 计算机科学, 2020, 47(11A): 430-436.
[8] 顾秋阳, 琚春华, 吴功兴. 融入深度自编码器与网络表示学习的社交网络信息推荐模型[J]. 计算机科学, 2020, 47(11): 101-112.
[9] 赵霞, 李娴, 张泽华, 张晨威. 结合社区嵌入和节点嵌入的社区发现算法[J]. 计算机科学, 2020, 47(10): 121-125.
[10] 孙永樾, 李红燕, 张金波. RAISE:一种高效的社交网络影响成本最小化算法[J]. 计算机科学, 2019, 46(9): 59-65.
[11] 刘小捷, 吕晓强, 王晓玲, 张伟, 赵安. 基于维基百科类别图的推特用户兴趣挖掘[J]. 计算机科学, 2019, 46(9): 79-84.
[12] 张征, 王宏志, 丁小欧, 李建中, 高宏. 社交网络中同一用户的识别[J]. 计算机科学, 2019, 46(9): 93-98.
[13] 石峻岭,王兴伟,黄敏. 一种内容中心型车载社交网络路由机制[J]. 计算机科学, 2019, 46(7): 50-55.
[14] 刘长赟,杨宇迪,周丽华,赵丽红. 带有时间标签的流行社交位置发现[J]. 计算机科学, 2019, 46(7): 186-194.
[15] 吕志泉, 李昊, 张宗福, 张敏. 基于主题模型的社交网络匿名用户重识别[J]. 计算机科学, 2019, 46(6): 143-147.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .