牛冬冬，陈鸿昶，金 鑫，刘力雄

（1.国家数字交换系统工程技术研究中心，河南 郑州450002；2.国家计算机网络与信息安全管理中心，北京100031）

0 引 言

复杂网络的网络结构存在着小世界特性、无标度特性以及网络节点的幂律分布等特性[1－3]。研究发现，实际的复杂网络并不是随机网络，而是具有一定的组织结构，绝大多数复杂网络的拓扑结构都呈现总体分散局部聚集的特征，即整个网络是由若干个 “群”或 “团”构成的，群内部的节点链接相对较紧密，但是各个群之间的链接相对而言却比较稀疏，研究者把这称为复杂网络的社区结构特性。复杂网络的社区发现对于复杂网络的拓扑结构分析、群体行为分析以及行为预测等具有重要的研究意义。

目前存在很多种社区发现方法，可以分类为全局社区发现方法和局部社区发现方法[4]。全局社区发现方法有图分割方法、层次聚类算法、分裂算法等等，由于全局社区发现方法进行社区发现时利用全局的网络信息，所以该类算法计算复杂度往往过高，而复杂网络的规模愈来愈大，所以该类算法的应用范围比较有限。局部社区发现方法是从点到面的信息挖掘，使用网络中的部分信息进行社区分析，因此有着全局社区发现方法不可比的效率，该类方法一般是选取网络中的一个起始节点进行社区结构的探测，通过发现不同的起始节点所在的社区达到发现全网社区的目的。但是该类社区发现方法的社区发现结果准确度往往较低，因为该类社区发现方法受限于起始节点，当起始节点为边界节点时发现的社区结构并不一定是网络中真实的社区结构。……