摘要
针对传统标签传播算法(LPA)中存在的输出结果不稳定和易形成巨型社区的缺陷,提出一种基于边权的稳定标签传播算法(SLPA_EW)用于社区发现.算法首先基于三角结构度量节点邻居的不同地位并将度量结果作为边权.接着,利用邻居中同一标签的边权累加值指导节点标签的更新过程,将随机的标签选择变为确定的选择,以保证算法输出结果的稳定性.标签初始化过程中,将边权互为最大值的相邻节点形成节点对并赋予相同标签,避免初始传播时出现标签振荡的问题.标签传播过程中,将标签权重加入到标签更新规则中以限制形成社区的规模,避免出现巨型社区的问题.真实网络数据集上的实验结果表明,所提算法能够保障输出的稳定性和质量,并且拥有较低的运行时间和迭代次数.
In order to avoid the instability of the output result and the defect of the giant community formation in the label propagation algorithm( LPA),a Stable Label Propagation Algorithm based on Edge Weights( SLPA_EW) for community detection is proposed.First,we measure the different statuses of node neighbors based on the triangle structure and uses the metrics as the edge weights.Next,the edge weights of the same label in the neighbors are used to guide the updating process of the node labels and the random label selection is changed to definitized selection to ensure the stability of the output of the algorithm. In order to avoid the label oscillation problem in the process of label initialization,take the strategy of forming node pairs and giving the same label to these nodes. In the process of label propagation,adding label weight to the label updating strategy limits the scale of community formation and avoids the problem of giant community. The experimental results on real network datasets showthat the proposed algorithm can guarantee the stability and quality of the output and have lowrunning times and iteration times.
引文
[1]Fortunato S,Hric D.Community detection in networks:a user guide[J].Physics Reports,2016,659(11):1-44.
[2]Zhang Hua-jian,Wang You-quan,Wu Zhi-ang,et al.Modularity optimization method for community detection based on local closeknit structures[J].Journal of Southeast University(Natural Science Edition),2014,44(3):504-509.
[3]Qiu Xiao-hui,Chen Yu-zhong.An improved particle-swarm-optimization algorithm for community discovery in social netw orks[J].Journal of Chinese Computer Systems,2014,35(6):1422-1426.
[4]Li Wei-min,Jiang Shu,Jin Qun.Overlap community detection using spectral algorithm based on node convergence degree[J].Future Generation Computer Systems,2018,79(1):408-416.
[5]Yang Jin-xuan,Zhang Xiao-dong.A spectral method to detect community structure based on distance modularity matrix[J].International Journal of M odern Physics B,2017,31(20):1750129.
[6]Zhao Shu,Ke Wang,Chen Jie,et al.Tolerance granulation based community detection algorithm[J].Tsinghua Science and Technology,2015,20(6):620-626.
[7]Kumar P,Gupta S,Bhasker B.An upper approximation based community detection algorithm for complex netw orks[J].Decision Support Systems,2017,96(4):103-118.
[8]Xu Cheng-lin,Chen Zhi-gang,Huang Rui,et al.LPA_LRDC tag propagation community discovery algorithm based on optimized LeaderRank[J].Journal of Chinese Computer Systems,2017,38(8):1746-1750.
[9]Berahmand K,Bouyer A.LP-LPA:a link influence-based label propagation algorithm for discovering community structures in netw orks[J].International Journal of M odern Physics B,2018,32(6):1850062.
[10]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale netw orks[J].Physical Review E Statistical Nonlinear&Soft M atter Physics,2007,76(3):96-106.
[11]Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E Statistical Nonlinear&Soft M atter Physics,2009,80(2):026129.
[12]Liu Xin,Murata T.Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica AStatistical Mechanics&Its Applications,2010,389(7):1493-1500.
[13]Xing Yan,Meng Fan-rong,Zhou Yong,et al.A node influence based label propagation algorithm for community detection in netw orks[J].The Scientific World Journal,2014,2014(5):210-223.
[14]Shang Rong-hua,Zhang Wei-tong,Jiao Li-cheng.Circularly searching core nodes based label propagation algorithm for community detection[J].International Journal of Pattern Recognition and Artificial Intelligence,2016,30(8):1659024.
[15]Ma Tian-ren,Xia Zheng-you.An improved label propagation algorithm based on node importance and random w alk for community detection[J].M odern Physics Letters B,2017,31(14):1750162.
[16]Zhang Wei-tong,Zhang Rui,Shang Rong-hua,et al.Weighted compactness function based label propagation algorithm for community detection[J].Physica A:Statistical M echanics and its Applications,2018,492(15):767-780.
[17]Newman M E J.Fast algorithm for detecting community structure in netw orks[J].Physical Review E Statistical Nonlinear&Soft M atter Physics,2004,69(6):066133.
[18]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[19]Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of longlasting associations[J].Behavioral Ecology&Sociobiology,2003,54(4):396-405.
[20]Girvan M,Newman M E J.Community structure in social and biological netw orks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[21]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E Statistical Nonlinear&Soft M atter Physics,2006,74(3Pt2):036104.
[22]Watts D J,Strogatz S H.Collective dynamics of‘small world’netw orks[J].Nature,1998,393(6684):440-442.
[23]Wang Xing-yuan,Li Jun-qiu.Detecting communities by the corevertex and intimate degree in complex netw orks[J].Physica A:Statistical M echanics and its Applications,2013,392(10):2555-2563.
[24]Xie Jie-rui,Szymanski B K,Liu Xiao-ming.SLPA:uncovering overlapping communities in social netw orks via a speaker-listener interaction dynamic process[C].Proc of the 11th IEEE International Conference on Data M ining Workshops,Washington DC:IEEEComputer Society,2011:344-349.
[2]张华健,王有权,伍之昂,等.基于局部紧耦合结构的模块性优化社区检测方法[J].东南大学学报(自然科学版),2014,44(3):504-509.
[3]邱晓辉,陈羽中.一种面向社会网络社区发现的改进粒子群优化算法[J].小型微型计算机系统,2014,35(6):1422-1426.
[8]徐成林,陈志刚,黄瑞,等.用于社区发现的LPA_LRDC标签传播算法[J].小型微型计算机系统,2017,38(8):1746-1750.
1http://w w w-personal. umich. edu/~mejn/netdata/
2 http://snap. stanford. edu/data/
