文档介绍：提 要
网络与人们的日常生活息息相关，而复杂网络普遍存在于网络之中。特别是进入信
息时代以来，人们已经越来越离不开网络。对复杂网络中社区结构的研究是复杂网络研
究中的重要一环，并且已经引起越来越多的学者的广泛关注。
对复杂网络中社区结构的研究包括动态网络、多关系网络和重叠社区等多个方向，
但是对静态网络的研究是其它方向的基础，也是当前最为广泛的研究方向。在社区发现
算法研究中已经提出了很多经典的算法，但是其中很多算法都以一些先验信息为前提
的，而这些先验信息往往是难以得到的，因此这也就限制了这些算法的推广和应用。
针对上述问题，本文首先提出了距离中心性的概念，距离中心性以节点间距离为基
础，同时包含节点中心性与相似度等概念。接着根据距离中心性提出了一种新的社区发
现算法，DCCD 算法。DCCD 算法是一种以距离中心性为基础的聚类算法，首先根据节
点中心性选取中心节点，然后由其它节点与中心节点的相似度确定社区归属，从而完成
对整个网络节点的社区划分。同时，基于距离中心性的概念又提出了距离中心度这一重
要节点评价指标。距离中心度不仅考虑了节点在网络中所处的位置，更加结合了节点与
其直接相邻节点间的连接关系和度数关系，以及其相邻节点对其中心性的贡献程度。
通过在一系列社区发现算法经典数据集上的实验证明，DCCD 算法在不需要提供太
多的先验信息前提下，就可以得到质量较高的社区划分，同时能够发现社区内部的隐含
结构；而距离中心度则具有更全面、更准确地衡量节点重要程度的优势。
摘 要
基于复杂网络的社区发现算法研究
在人类社会和自然界中，个体间及与周围环境间相互影响、相互作用，共同构成了
随处可见的复杂网络，如社会关系中的科学家协作网络、流行病传播网络，生态系统中
的新陈代谢网络、蛋白质交互网络等等，特别是进入信息时代以来，互联网技术的发展
又使世界变的更小了，而人与人之间的联系更加紧密了，人类社会已经逐步演变成了一
个网络的世界。因此，对复杂网络的研究也越来越成为一项热点的研究课题。
复杂网络由于其自身具有规模庞大、节点及连接复杂等特点，直接对复杂网络整体
进行研究往往具有一定难度，而社区作为复杂网络中的一个重要属性，对复杂网络中社
区的研究已经引起了越来越多的关注和重视。对复杂网络中社区发现的研究，一方面是
挖掘其中的社区结构，进而发现其社区划分；另一方面是对网络的节点重要性进行评估，
发掘其中的重要节点。
近些年，对复杂网络的社区发现算法的研究取得了长足的发展，也出现了很多经典
的社区发现算法，如 GN 算法、K-L 算法等。但是其中很多算法都需要提供社区划分个
数、社区规模大小等一些先验信息，而这些先验信息一般情况下是事先难以得到的。对
于能够提供准确先验信息的情况，这些算法能够得到较为准确的社区划分，但是，如果
无法得到较为准确的先验信息，这些算法往往得到的划分结果不是令人十分满意的。
本文通过对复杂网络及社区发现等相关文献的阅读，充分了解了复杂网络中社区发
现算法的类别及相关特点，分析与总结了一些经典社区发现算法的优点与不足。此外，
本文深入研究了网络中节点中心性及节点间的相似度等问题，同时针对上述社区发现算
法的不足，首先提出了距离中心性的概念，并分别提出了基于距离中心性的社区发现算
法（DCCD 算法）和基于距离中心性的重要节点评价指标。
距离中心性以节点间距离为基础，同时包含节点中心性与相似性等概念。DCCD 算
法以节点间的距离中心性为标准，通过其中心性来选取中心节点，然后通过相似性来判
断其它节点的社区归属，从而完成对整个网络的社区划分。在完成社区划分后，采用
K-means 算法思想对所得到的社区继续以距离中心性为基础进行迭代计算，重新计算各
个社区的中心节点，并以此重新进行社区划分，直至网络达到稳定结构。而距离中心性
评价指标，不仅考虑了节点在网络中所处的位置，更加结合了节点与其直接相邻节点间
的连接关系和度数关系，以及其相邻节点对其中心性的贡献程度。因此，距离中心性评
价指标具有更全面的衡量标准。
为验证 DCCD 算法以及距离中心性评价指标的正确性，将其在空手道俱乐部数据集