融合影响力和标签传播的社团划分算法  

A community division algorithm integrating influence and label propagation

作　　者：李谢君 李玲娟[1] LI Xiejun;LI Lingjuan(School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,江苏南京210023

出　　处：《南京邮电大学学报（自然科学版）》2024年第5期95-101,共7页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：国家重点研发计划专项(2020YFB2104002);江苏省重点研发计划(BE2019740)资助项目。

摘　　要：针对传统标签传播算法因在节点更新序列初始化和标签更新过程中采用随机策略而导致的社团划分结果不稳定和准确度较低的问题,设计了一种融合影响力和标签传播的社团划分算法(ILPCD)。首先,基于k-shell算法对网络进行层次划分,并利用节点及其一阶邻居节点的k-shell值计算节点在网络中的全局影响力,并按照全局影响力的降序来初始化节点更新序列,消除更新顺序的随机性;然后,引入平滑系数对Jaccard相似系数的计算方法进行改进,更客观地衡量节点之间的关联性,得到节点的局部影响力;最后,依据局部影响力来更新标签,消除标签传播过程中的随机性。在4种真实网络数据集上的实验结果表明,ILPCD算法能够有效地对社团进行划分,并且具有更高的稳定性和准确性。Since traditional label propagation algorithms adopt random strategies during node update sequence initialization and label update,their community division results usually face instability and low accuracy.In regard of this,we design a community division algorithm integrating influence and label propagation,namely ILPCD.First,the network is hierarchically divided by the k-shell algorithm.The global influence of each node in the network is calculated by its k-shell value and its first-order neighboring nodesk-shell values.Then,the node update sequence is initialized in descending order of the global influences,thus the randomness of the update sequence can be eliminated.Second,the calculation method for Jaccard similarity coefficient is improved by introducing a smoothing coefficient,thus the correlation between nodes can be more objectively measured and the nodeslocal influences can be obtained.Finally,labels are updated according to the local influences,and the randomness in the process of label propagation can also be eliminated.Experimental results on four real network datasets show that the ILPCD algorithm can effectively divide communities,and has higher stability and accuracy.

关 键 词：社团划分 影响力 k-shell算法 相似系数 

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