赵宝峰，赵菊敏，李灯熬

（太原理工大学a．矿业工程学院；b．信息工程学院，太原030024）

现实世界纷繁复杂，各种事物之间存在着普遍的联系和彼此的依赖。许多这样的复杂系统可以用复杂网络来建模表示，并通过网络分析与挖掘方法对系统进行深入的研究。20世纪末，人类对复杂网络的认识有了突破性进展，除了众所周知的小世界特性［1］和无标度特性［2］外，科学家们还发现各类复杂网络中普遍存在着社区结构［3］。所谓社区结构是指网络中内部连接较为紧密而彼此连接较为松散的子结构。在现实世界中，社区结构往往对应着各类系统中不同的功能与结构。例如社会网络中的组织团体、生物蛋白质相互作用网络中的蛋白复合体以及电路网络中的各个功能模块等。因此，发现网络中的社区结构对深入了解系统的功能和结构有着非常重要的意义。

经过近十年的发展，已经有许多种社区发现算法被提出。GN算法［4］由Newman等人提出，它通过割断中介度指标大的边将网络进行分裂从而发现社区结构。BGLL算法［5］是一种基于模块度指标的贪心优化算法，可以发现有层次的社区结构。Infomap算法［6］是一种利用随机游走和信息论的算法，是目前公认的准确率较高的一种算法。此外，在各种算法当中，有一类具有接近线性时间复杂度的算法，称为标签传播算法［7］（Label Propagation Algorithm，LPA）。该算法的优点是计算过程非常简单，计算速度非常之快，但缺点是算法的稳定性较差，连续几次运行结果可能会很不相同。……