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

Survey on Online Influence Maximization

作　　者：孔芳 李奇之 李帅[3] KONG Fang;LI Qi-zhi;LI Shuai(School of Software,Shandong University,Jinan 250101,China;School of Computer Science and Technology,Xidian University,Xi’an 710071,China;John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 201100,China)

机构地区：[1]山东大学软件学院,济南250101 [2]西安电子科技大学计算机科学与技术学院,西安710071 [3]上海交通大学约翰·霍普克罗夫特计算机科学中心,上海201100

出　　处：《计算机科学》2020年第5期7-13,共7页Computer Science

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]