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

摘要： 社区结构是复杂网络最重要的一种结构特征。复杂网络中的社区结构研究主要包括社区发现与关键节点发掘两个重要问题。基于节点中心性的社区发现算法可同时进行关键节点发掘与社区发现。针对传统局部Fiedler向量中心性（LFVC）算法存在关键节点识别准确率低，进行社区发现时易出现孤立节点等问题，提出了节点局部Fiedler向量中心性差值社区发现算法（CDDN），设计了新的关键节点识别与边移除策略，并分析了算法性能。选择3种具有代表性的社区发现算法分别在4个真实复杂网络数据集上进行对比实验。实验结果表明，改进的算法既保持了局部中心性度量方法的效率，也防止了错误识别关键节点和关键边对划分结果的负面影响，避免了孤立点所带来的社区结构信息损失，能够快速、准确地发现真实社区。

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