基于相似度投票的社区划分改进算法  

Improved Community Partition Algorithm Based on Similarity Voting

作　　者：冯成强 左万利[1] 王英[1] FENG Chengqiang;ZUO Wanli;WANG Ying(College of Computer Science and Technology, Jilin University, Changchun 130012, China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（理学版）》2018年第3期601-609,共9页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:60973040);国家自然科学基金青年科学基金(批准号:61602057)

摘　　要：为快速、准确地对日益复杂的大规模社会网络进行社区划分,提出一种基于相似度投票的改进算法替代Louvain算法的底层划分,解决了Louvain算法在底层划分收敛速度较慢,并出现大量重复计算的缺点,使社区划分更迅速.由真实社会网络数据实验结果可见,与Louvain算法相比,改进算法在保持模块度基本不变的情况下,效率显著提高,划分的社区数更少、社区结构更紧凑.In order to quickly and accurately partition the community of large-scale social networks which were increasingly complicated,we proposed an improved algorithm based on similarity voting to replace the underlying partition of Louvain algorithm.It solved the shortcomings of Louvain algorithm such as slow convergence in the bottom partitioning and large number of double counting,which made the community partition more rapidly.The experimental results from real social network data show that compared with the Louvain algorithm,the efficiency of the improved algorithm is much higher,with less number of communities partitioned,and the community structure is more compact in the case of keeping the modularity basically unchanged.

关 键 词：社会网络 社区划分 相似度投票 Louvain算法 模块度 社区数 社区结构 

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