New algorithm of detecting community structure based on degree centrality
Dai Ai-ming · Jisuanji yingyong yanjiu · 2011
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.