一种基于聚集系数的局部社团划分算法  

Local Community Detecting Method Based on the Clustering Coefficient

作　　者：李孔文[1] 顾庆[1] 张尧[1] 陈道蓄[1] 

机构地区：[1]南京大学计算机科学与技术系软件新技术国家重点实验室,南京210093

出　　处：《计算机科学》2010年第7期46-49,53,共5页Computer Science

基　　金：863国家高技术研究发展计划(2006AA01Z177);国家自然科学基金(60873027)资助

摘　　要：社团划分算法是复杂网络研究中的一个热点问题。传统的复杂网络社团划分算法都必须获得全局网络的信息。随着网络规模不断增大,获得全局信息的难度随之增加;而在很多情况下只关心网络中某节点所在的局部社团。为了准确、快速地找到大规模复杂网络中的局部社团,提出了一种基于节点聚集系数性质的局部社团划分算法。该算法根据节点的连接频度,利用节点聚集系数的性质,从网络中某一待求节点开始,通过搜索邻居节点,划分该节点的社团结构。该算法只需要了解与待求节点相关的局部网络信息,在解决局部社团划分问题时其时间复杂度比传统的社团划分算法低。同时,该算法也可以应用于复杂网络全局社团结构的划分。利用该算法分别对Zachary空手道俱乐部网络和由Java开发工具包构成的软件网络图进行社团划分实验,并且分别对实验结果与对象网络的具体特征进行了对比分析。Community detecting has been a research topic in the complex network area. The global information of the whole network, which is required by the traditional community detecting algorithms, is hard to get when the scale of the network grows. On the other hand, in many cases we only care about the local community of one particular node of the network. To make the local community detecting faster and more accurate, this paper proposed a local community detecting method based on the clustering coefficient of the nodes. The proposed method, which leverages the connectivity density and the characteristics of clustering coefficient, starts from the target node of the network and detects the community it belongs to by searching the neighbor nodes. This method requires only the local network information related to the target node and is faster compared to the traditional community detecting algorithm. It is also applicable for global community structure detecting. The method was applied to the Zachary network and JSCG, and the experiment results were analyzed by comparing with the actual characteristics of the object network.

关 键 词：局部社团 聚集系数 社团划分 

分 类 号：TP11[自动化与计算机技术—控制理论与控制工程]