郑文萍 ,刘美麟 ,穆俊芳 ,杨 贵

（1.山西大学计算机与信息技术学院，太原，030006；2.计算智能与中文信息处理教育部重点实验室，山西大学，太原，030006；3.山西大学智能信息处理研究所，太原，030006）

现实世界中的许多复杂系统都可以抽象成网络，如社交网络、基因调控网络、交通运输网络、电力传输网络、引文网络等［1-4］.社区结构是复杂网络的重要特征，即一个网络中节点形成了若干个社区，社区内部节点连接相对紧密，社区间节点连接相对稀疏.网络中的社区通常对应复杂系统中的一些特殊功能模块，如社交网络中具有某种特定关系的群体、基因调控网络中特定生物功能的蛋白质复合体、互联网中具有相同主题的网站集合、引文网络中相同兴趣的研究群体等.在网络上进行图聚类分析，可以挖掘网络中的潜在社区，为分析和理解复杂系统的拓扑结构及动力学特性提供指导［5］.

1 相关工作

研究者已提出许多社区检测算法，主要分为基于模块度优化的算法、基于谱聚类的算法、基于信息传播的算法等.也有许多用于评价社区划分结果好坏的模块度指标，使用最广泛的是2004 年Newman and Girvan［6］提出的模块度.许多基于模块度优化的算法被提出，如BGLL［7］，Leiden［8］等，其基本思想是从对网络节点所有可能的划分中寻找使得模块度最大的社区划分，通常可以找到满足社区定义的较稳定的社区划分结果，但由于计算代价较高且受模块度的精度限制［9］，此类算法通常不适用于大规模网……