一个基于中心度的社团结构发现新算法  

New algorithm of detecting community structure based on degree centrality

作　　者：戴爱明[1,2] 高学东[1] 王立敏[3] 

机构地区：[1]北京科技大学经济管理学院,北京100083 [2]南昌航空大学制造业发展研究所,南昌330063 [3]北京科技大学中国教育经济信息网管理中心,北京100083

出　　处：《计算机应用研究》2011年第8期2909-2911,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(70962008);国家航空科学基金资助项目(2009ZG56022)

摘　　要：针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法(DCGN)。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Za-chary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算法均具有一定的优势。Using GN algorithm to detect the community structure,there will be high time complexity.This paper proposed a new GN algorithm based on degree centrality（DCGN）.According to node degree centrality and the shortest path among them,the algorithm first confirmed the community structure central nodes,then deleted edges with the biggest betweenness among the community structure central nodes by step,to finish the community structure dividing.This algorithm got rid of high cost of parameter calculating when using GN algorithm,the algorithm ran in time O（cmn） when c was a constant,n was the number of network member,m was the number of network edge.Applied both this algorithm and GN algorithm to Zachary net and the net generated randomly by computer,and then compared them.Experiment results shows the proposed algorithm has advantage in feasibility and effectiveness.

关 键 词：社团结构 节点中心度 GN算法 DCGN算法 

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