基于Leiden社区划分的节点影响力最大化  

Influence Maximization of Nodes Based on Leiden Community Division

作　　者：许雪 陈伯伦 王笑颜 李哲 于翠莹 赵月 XU Xue;CHEN Bolun;WANG Xiaoyan;LI Zhe;YU Cuiying;ZHAO Yue(School of Computer and Software Engineering,Huaiyin Institute of Technology,Huai’an Jiangsu)

机构地区：[1]淮阴工学院计算机与软件工程学院,江苏淮安223003

出　　处：《淮阴工学院学报》2024年第2期60-67,95,共9页Journal of Huaiyin Institute of Technology

基　　金：国家自然科学基金项目“动态多关系网络中影响力最大化问题的研究”(61602202);教育部人文社科基金项目“基于复杂网络的突发卫生事件中舆情防控机制研究”(22YJZH014)。

摘　　要：随着大数据时代的到来,网络规模急剧增长,迫切需要研究在大规模社会网络环境下影响力最大化问题的高效求解方法。考虑到真实的社会网络往往具有明显的社区结构,提出了一种基于社区划分的影响力最大化算法。该算法首先利用Leiden算法对社区网络按模块度进行划分来降低搜索空间;其次在子社区内使用基于中心性的PageRank改进算法来进行种子节点的选取;最后通过在传染病模型SIR(Susceptible Infected Recovered Model,SIR)上对节点的传播影响力进行模拟。通过对3个真实社交网络数据集的实验研究后发现,该算法通过在各社区内寻找影响力节点,不但具有较高的准确性,而且时间复杂度较低。With the arrival of the big data time and the rapid growth of network size,there is an ur-gent need to study efficient methods for solving influence maximization problems in large-scale social network environments.Moreover,real social networks often have obvious community structure,and finding influence nodes within each community can effectively reduce the computational cost.To this end,the community partitioning algorithm is proposed to divide large-scale social networks into multiple communities so that the search space is significantly reduced,and the influence maximization study is carried out on this basis as follows:firstly,the community network is partitioned by modularity using Leiden's algorithm;secondly,the top-k seed nodes are selected within each community using the improved PageRank algorithm based on centrality;finally,the final influence scale of seed nodes on the SIR model was tested.Through extensive experimental studies on five real social network datasets,the validation shows the efficiency and effectiveness of the proposed scheme.

关 键 词：影响力最大化 Leiden算法 PAGERANK算法 SIR模型 

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