基于最小社团链接度增量的社团结构挖掘算法  

Mining algorithm of community structure based on the minimal increment of link degree of a community

作　　者：王立敏[1,2] 高学东[1] 武森[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083 [2]北京科技大学中国教育经济信息网管理中心,北京100083

出　　处：《北京科技大学学报》2009年第1期112-117,共6页Journal of University of Science and Technology Beijing

基　　金：教育部新世纪优秀人才支持计划资助项目(No.NCET-05-0097)

摘　　要：针对复杂网络社团结构挖掘算法复杂度高的问题,定义了一个衡量局部社团结构的指标,提出了一种基于最小社团链接度增量的社团结构挖掘算法.本算法的时间复杂度为O(kd),其中d为网络的平均节点度数,k为搜索的节点数.为了验证本算法的性能和计算的准确性,把本算法与一种经典的挖掘局部社团结构方法——Clauset算法,进行了比较.实验结果表明:本算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有了显著提高.A measure of local community structure was defined, and an mining algorithm of local community structure based on the minimal increment of link degree of a community was presented for resolving the time complexity problems of finding local com- munity structure in complex networks. The algorithm ran in time O （led） for general graphs, where d is the mean degree and k is the number of vertices to be explored. In order to determine its performance and calculation precision, the algorithm was compared with the classical local community identification approach, Clauset algorithm. Experimental results show that mining results of the algorithm are as effective as those of Clauset algorithm on the whole, and the algorithm is much faster than Clauset algorithm.

关 键 词：复杂网络 链接度 社团结构 挖掘算法 

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