计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 7-13.doi: 10.11896/jsjkx.200200071
所属专题: 理论计算机科学
孔芳1, 李奇之2, 李帅3
KONG Fang1, LI Qi-zhi2, LI Shuai3
摘要: 影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。
中图分类号:
[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 |
|