计算机应用研究2011，Vol.28Issue(8)：2909-2911,3.DOI:10.3969/j.issn.1001-3695.2011.08.030
一个基于中心度的社团结构发现新算法
New algorithm of detecting community structure based on degree centrality
摘要
Abstract
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算法Key words
community structure/ degree centrality/ GN algorithm/ DCGN algorithm分类
信息技术与安全科学引用本文复制引用
戴爱明,高学东,王立敏..一个基于中心度的社团结构发现新算法[J].计算机应用研究,2011,28(8):2909-2911,3.基金项目
国李自然科学基金资助项目(70962008) （70962008）
国家航空科学基金资助项目(2009ZG56022) （2009ZG56022）
