关键词: 复杂网络, 社区发现, 关键节点发掘, 中心性, 图分割算法

Abstract: Community structure is one of the most important structural characteristics of complex networks, on which the research mainly includes two important issues such as community detection and key nodes mining. Community discovery algorithm based on centrality is a kind of algorithm which can solve these two types of issues simultaneously. A community detection algorithm by difference with node-local Fiedler vector centrality (CDDN) is proposed, in order to solve the problems of key nodes misidentification and isolated node occurrence in the traditional local Fiedler vector centrality algorithm. In CDDN, a new key nodes identification and edge removal rule is designed, and the algorithm performance is analyzed. Three representative community detection algorithms are selected to carry out comparative experiments on 4 real network datasets. Experimental results show that the new algorithm not only has the same efficiency of the local centrality measurement method, but also prevents the negative impact of misidentification of key nodes and edges on the partitioning results, and the loss of community information caused by isolated node. It can discover the real community quickly and accurately.

Key words: complex network, community detection, key nodes mining, centrality, graph partition algorithm