[1]张 猛,李玲娟.稳定的标签传播社团划分算法研究[J].计算机技术与发展,2020,30(01):129-134.[doi:10. 3969 / j. issn. 1673-629X. 2020. 01. 023]
　ZHANG Meng,LI Ling-juan.Research on Stable Label Propagation Community Division Algorithm[J].Computer Technology and Development,2020,30(01):129-134.[doi:10. 3969 / j. issn. 1673-629X. 2020. 01. 023]
点击复制

稳定的标签传播社团划分算法研究()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
30
期数:
2020年01期
页码:
129-134
栏目:
应用开发研究
出版日期:
2020-01-10

文章信息/Info

Title:
Research on Stable Label Propagation Community Division Algorithm
文章编号:
1673-629X(2020)01-0129-06
作者:
张 猛; 李玲娟
南京邮电大学 计算机学院,江苏 南京 210023
Author(s):
ZHANG Meng; LI Ling-juan
School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
关键词:
复杂网络; 社团划分; 标签传播; 综合影响力
Keywords:
complex network; community division; label propagation; comprehensive influence
分类号:
TP311
DOI:
10. 3969 / j. issn. 1673-629X. 2020. 01. 023
摘要:
快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。 标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。 为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。 该算法利用改进的 K-Shell 算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。 在真实网络和人工合成网络上的实验结果表明,S-LPA 算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。
Abstract:
The rapid and stable discovery of community in complex networks is a hot topic in the study of community division in recent years. Label propagation algorithm (LPA) has a nearly linear time complexity and can quickly discover the community structure in complex networks,but it has uncertainty and randomness in the process of label propagation,which reduces the accuracy and stability of the partition results. To solve this problem,we design a stable label propagation community division algorithm (S-LPA). The improved K-shell algorithm is used to calculate the global influence of nodes,and the comprehensive influence of nodes is calculated by combining the global influence and the degree value that can reflect the local influence of nodes with the information of neighbor nodes. Then the labels are updated according to the label influence in the process of label propagation. When the labels of all nodes in the network no longer change or the number of iterations reaches the maximum,the nodes with the same label are assigned into the same community. The experimental results on real networks and synthetic networks show that the S-LPA algorithm not only has linear time complexity,but also significantly improves the quality and stability of community division.

相似文献/References:

[1]李方洁 刘希玉.复杂网络维的测量[J].计算机技术与发展,2010,(04):61.
　LI Fang-jie,LIU Xi-yu.Measuring Dimensions for Complex Networks[J].Computer Technology and Development,2010,(01):61.
[2]李晶晶 王红.用复杂网络理论分析电网及大停电事故[J].计算机技术与发展,2008,(10):247.
　LI Jing-jing,WANG Hong.Analysis on Power Grids and Blackouts with Complex Network Theory[J].Computer Technology and Development,2008,(01):247.
[3]惠伟 王红.复杂网络在城市公交网络中的实证分析[J].计算机技术与发展,2008,(11):217.
　HUI Wei,WANG Hong.Empirical Analysis of Complex Networks in Public Traffic Networks[J].Computer Technology and Development,2008,(01):217.
[4]赵鹏 蔡庆生 王清毅.一种用于文章推荐系统中的用户模型表示方法[J].计算机技术与发展,2007,(01):4.
　ZHAO Peng,CAI Qing-sheng,WANG Qing-yi.A Novel Representation of User Profile in Document Recommendation System[J].Computer Technology and Development,2007,(01):4.
[5]赵鹏 耿焕同 蔡庆生 王清毅.一种基于加权复杂网络特征的K—means聚类算法[J].计算机技术与发展,2007,(09):35.
　ZHAO Peng,GENG Huan-tong,CAI Qing-sheng,et al.A Novel K- means Clustering Algorithm Based on Weighted Complex Networks Feature[J].Computer Technology and Development,2007,(01):35.
[6]顾亦然 谢鸿飞 李金发.移动通信网络中人类行为动力学的研究[J].计算机技术与发展,2010,(09):57.
　GU Yi-ran,XIE Hong-fei,LI Jin-fa.Studies Based on Complex Network and Dynamics of Human Behavior in MC Network[J].Computer Technology and Development,2010,(01):57.
[7]顾亦然 李金发 谢鸿飞.阵发特性影响因素的研究[J].计算机技术与发展,2010,(09):168.
　GU Yi-ran,LI Jin-fa,XIE Hong-fei.Study on Influence Factors of Characteristic of Burst[J].Computer Technology and Development,2010,(01):168.
[8]朱永真 夏正友 卜湛 刘新建.虚拟社区中的社团结构研究与分析[J].计算机技术与发展,2011,(01):46.
　ZHU Yong-zhen,XIA Zheng-you,BU Zhan,et al.Research and Analysis on Community Structure in Virtual Community[J].Computer Technology and Development,2011,(01):46.
[9]何明东 熊建斌 李振坤.基于复杂网络的软件开发方法研究[J].计算机技术与发展,2011,(06):59.
　HE Ming-dong,XIONG Jian-bin,LI Zhen-kun.Complex Network-Based Software Development Method Research[J].Computer Technology and Development,2011,(01):59.
[10]王泽洪 闵妍妮 刘名扬 谭韵天.Pub/Sub系统中基于免疫的新型路由算法[J].计算机技术与发展,2012,(02):6.
　WANG Ze-hong,MIN Yan-ni,LIU Ming-yang,et al.A New Immunity-Based Routing Strategy in Pub/Sub System[J].Computer Technology and Development,2012,(01):6.

更新日期/Last Update: 2020-01-10