基于节点相似度和标签传播的加权网络社团划分方法  

A weighted network community division method based on node similarity and label propagation

作　　者：张鑫杰 李玲娟[1] ZHANG Xinjie;LI Lingjuan(School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

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

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

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

摘　　要：社团是复杂网络中连接紧密的节点所构成的群体,社团划分是理解网络结构和挖掘网络所蕴含的信息的有效途径,加权网络能比无权网络反映更深层次的信息,对其进行社团划分具有重要的现实意义。为了提高加权网络社团划分的准确性和效率,设计了一种基于节点相似度和标签传播的加权网络社团划分方法SLWCD。该方法用改进的Jaccard相似系数计算加权网络的节点相似度,并基于节点相似度将节点分组,再按组分配初始标签;在标签传播过程中,对目标节点的邻居节点按标签分组,将目标节点的标签更新为与其边权之和最大的组所对应的标签;当标签不再变化时,将具有相同标签的节点归于同一个社团,产生最终的社团划分结果。在Zachary空手道俱乐部网络和Lesmis网络上的实验结果表明,SLWCD方法不仅能够准确地划分加权网络的社团,而且具有较高的稳定性和较低的时间复杂度。Community is a group composed of closely connected nodes in a complex network.Community division is an effective way to understand the network structure and mine the information contained in the network.A weighted network can reflect deeper information than an unweighted one,so weighted network community division has important practical significance.In order to improve the accuracy and efficiency of weighted network community division,a weighted network community division method based on node similarity and label propagation,named SLWCD,is designed.First,the improved Jaccard similarity coefficient is used to calculate the node similarity of the weighted network.The nodes are grouped based on the similarity,and the initial labels are assigned according to groups.Second,in the process of label propagation,the neighbor nodes of the target node are grouped by the labels,and the target node label is updated to the label corresponding to the group with the largest sum of its edge weights.When the labels are no longer changed,the nodes with the same label are classified into the same community,and the final community division result is produced.The experimental results on the Zachary karate club network and the Lesmis network show that the proposed SLWCD can accurately divide the communities of weighted networks,and has high stability and low time complexity.

关 键 词：加权网络 社团划分 节点相似度 更新策略 标签传播 

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