基于共邻节点贡献度的社团划分算法  

Community Division Algorithm Based on Contribution of Common Neighbor Nodes

作　　者：付立东[1] 武鑫 雍泽旭 FU Li-dong;WU Xin;YONG Ze-xu(College of Computer Science and Technology,Xi'an University of Science and Technology,Xi'an Shaanxi 710699,China)

机构地区：[1]西安科技大学计算机科学与技术学院,陕西西安710699

出　　处：《计算机仿真》2025年第1期382-389,共8页Computer Simulation

基　　金：国家自然科学基金(61772394,12071367);陕西省自然科学基础研究计划项目(2023-JC-YB-517)。

摘　　要：在复杂网络中高质量的社团划分会更好地揭示网络的结构特性与功能。基于节点相似性的算法是一类具有代表性的社团划分算法,但现有的基于节点相似性算法没有充分考虑到共邻节点之间的联系导致准确率下降。针对上述问题,首先定义共邻节点贡献度概念,提出一种基于共邻节点贡献度的社团划分算法(Contribution of Common Neighbor Nodes Based Community Division Algorithm, CCNNA),将共邻节点之间的连边数参与到RA相似度指标的计算当中,提高了度量的准确性;然后运用改进的层次聚类与最优模块度值的思想实现网络的社团划分。在人工合成网络与真实网络上的实验结果表明,所提算法能够很好地挖掘社团结构,与模块度优化CNM(Clauset-Newman-Moore)算法以及最新的基于节点相似性算法相比,所提算法有更高的社团模块度和划分准确率。In complex networks,high-quality community division can better reveal the structural characteristics and functions of the network.The algorithm based on node similarity is a kind of representative community division algorithm,but the existing algorithm based on node similarity does not fully consider the connection between common neighborhood nodes,resulting in a decline in accuracy.To solve this problem,this paper first defines the concept of the contribution of common neighborhood nodes.A Contribution Of Common Neighbor Nodes Based Community Division Algorithm(CCNNA)is proposed.The number of adjacent nodes involved in the calculation of the RA similarity index improves the accuracy of measurement.Then,the idea of improved hierarchical clustering and optimal modularity value is used to realize community division.Experimental results on synthetic networks and real networks show that the proposed algorithm can mine community structure well.Compared with the CNM(Clauset-Newman-Moore)algorithm based on modularity optimization and the latest node similarity algorithms,the proposed algorithm has higher community modularity and partition accuracy.

关 键 词：复杂网络 社团划分 共邻节点贡献度 层次聚类 模块度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]