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

New algorithm of detecting community structure based on degree centrality

针对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.