徐步东

(山东师范大学 信息技术管理处，济南 250014)

引言

现实世界中有大量的系统可以用由一些点和连接各个节点的边组成的网络来表示，如万维网、食物链网络。节点是表示复杂系统的基本单元，节点间的边表示各个单元的相互作用。系统中的每个节点以及每条边的性质都可以用称为“权重”和“强度”的更多信息来描述。

随着复杂网络研究的深入，人们注意到大量的实际网络都具有社团结构性质，即一个完整的实际网络通常是由若干个“社团”构成。我们着力研究实际网络的社团结构，从而有利于人们更加深入地了解网络结构以及分析网络的特性，使人们更加有效地理解和利用这些网络。例如，在发现社团以及社团的边界后我们可以根据结点的拓扑位置对结点进行分类，处于社团边界上的结点成为社团之间联系的桥梁，整个社团中心结点则控制着整个社团的稳定性。

1 复杂网络中社团发现算法研究现状

复杂网络中社团发现算法的一个主要目标是根据整个网络的拓扑结构来寻找网络中所存在的社团。社团发现与复杂网络的层次聚类和计算机科学图论中图分割的思想密切相关。层次聚类方法主要分为两类:凝聚方法(Agglomerative Method)和分裂方法(Divisive Method)。图分割主要包括两个算法:基于Laplacian 图特征值的谱平分法(Spectral Bisection Method)和Kernighan-Lin 算法。

Girvan 和Newman 提出了一类优化模块度Q 的算法，其中主要有极值优化算法以及模拟退火算法等，优化模块度算法的时间复杂度较高。……