基于标签传播的加权网络重叠社团划分算法

Overlapping community division algorithm of weighted network based on label propagation

针对加权复杂网络重叠社团划分的问题,提出一种基于SLPA算法改进的加权网络重叠社团划分算法。首先,采用PageRank升序序列固定标签传播顺序;其次,以标签的权重和为依据选择标签;最后,消除嵌套包含的社团结果。为验证算法,选择两种经典算法在人工仿真网络和真实网络中进行测试。结果表明:所提算法在不同划分难度下的加权LFR基准网络中重叠标准互信息(NMI)值均高于对比算法;在五个真实网络中的扩展模块度(EQ)和划分密度(PD)均高于对比算法。相较于SLPA算法,所提算法具有更好的适用性,能够发现高质量的社团结构。

To solve the problem of overlapping communities division in the weighted complex networks,an improved algorithm for dividing overlapping communities in weighted networks based on SLPA algorithm is proposed.Firstly,the PageRank ascending sequence is used to fix the tag propagation sequence.Secondly,the label is selected based on the weight sum of the labels.Finally,the community results contained in the nesting is eliminated.In order to verify the algorithm,two classical algorithms are tested in artificial simulation network and real network.The results show that the overlapping Normalized Mutual Information(NMI)values of the proposed algorithm are higher than those of the contrast algorithm in weighted LFR benchmark networks with different division difficulties.The Extended Modularity(EQ)and Partition Density(PD)in five real networks are higher than those in the comparison algorithm.Compared with SLPA algorithm,the proposed algorithm has better applicability and can find high-quality community structure.