基于局部传播中心性的影响力最大化算法  

THE INFLUENCE MAXIMIZATION ALGORITHM BASED ON LOCAL PROPAGATION CENTRALITY

作　　者：方辉 姜久雷 李盛庆 李卫民[3] Fang Hui;Jiang Jiulei;Li Shengqing;Li Weimin(College of Computer Science and Engineering,North Minzu University,Yinchuan 750021,Ningxia,China;College of Computer Science and Engineering,Changshu Institute of Technology,Suzhou 215500,Jiangsu,China;School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]常熟理工学院计算机科学与工程学院,江苏苏州215500 [3]上海大学计算机工程与科学学院,上海200444

出　　处：《计算机应用与软件》2023年第2期259-264,共6页Computer Applications and Software

基　　金：国家自然科学基金项目地区项目(61762002);国家重点研发计划项目(2017YFE0117500);教育部人文社会科学研究青年基金项目(18YJC870011);常熟理工学院科研启动基金项目(KYZ2018008Q);北方民族大学研究生创新项目(YCX20089)。

摘　　要：针对度中心性等方法选择种子节点时未考虑节点间传播概率及邻居拓扑连接的影响,提出局部传播中心性LPC(Local Propagation Centrality)的概念。为减少贪心算法时间复杂度高且不可扩展的问题,提出一种新的启发式算法IMLPC(Influence Maximization Algorithm based on LPC)。该算法通过计算每个节点的LPC,依次选择影响力最大的节点。实验结果表明,IMLPC的影响范围和运行时间较现有启发式算法相比有显著提升。在不同数据集下,IMLPC影响范围稳定、可扩展性好。Aimed at the problem that when the degree centrality and other methods select seed nodes,the propagation probability between nodes and the influence of neighbor topology connections are not considered,the concept of local propagation centrality(LPC)is proposed.In order to reduce the high time complexity and non-scalability of the greedy algorithm,a new heuristic algorithm IMLPC(Influence Maximization Algorithm based on LPC)was proposed.The algorithm calculated the LPC of each node and selected the most influential node in turn.The experimental results show that the influence range and running time of the IMLPC algorithm are significantly improved compared with the existing heuristic algorithms.Under different data sets,the IMLPC algorithm has a stable range of influence and good scalability.

关 键 词：社交网络 影响力最大化 传播概率 局部传播中心性 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]