一种面向复杂网络的快速模块结构识别算法

隋超，李文刚，白亮

（1.山西省农业科学院（山西农业大学）畜牧兽医研究所，山西 太原 030032；2.山西大学 智能信息处理研究所，山西 太原 030006）

0 引言

模块结构是复杂网络的一个普遍存在且重要性质，也被称为“社区结构”[1-2]。直观理解，在网络中一个模块（簇）由一组结点的连接群构成，这些结点相互联系非常紧密但与网络中其他密集群的结点连接稀疏。识别其模块结构已成为一种探索和理解网络如何工作的重要任务之一[3]。

由于在众多复杂系统中数据以网络形式存在[4]，如生物中的蛋白质互作用网络、基因调控网络、代谢网络等，越来越多学者关注于复杂网络的模块结构分析。为了解决该问题，各种各样的识别方法已经发展，包括潜在空间模型[5-7]、块模型近似[8]、标签传播模型[9]、模块最大化[10-11]、信息论模型[12]和重叠社区识别[13-14]等。根据不同的用户需求，这些模型有着不同的社区定义或识别标准，已被成功地应用到了不同的领域。潜在空间模型主要将网络中结点映射到低维欧式空间，这样基于网络连接性的结点之间接近度被保持在新的空间，然后通过利用传统聚类算法在低维空间中完成结点划分。块模型近似是将模块划分问题看作一个矩阵分块问题，即通过隶属关系对结点进行重新排序并利用块结构近似给定的网络。标签传播模型主要使用每个结点的邻近点信息来决定该结点的标签，不需要任何社区结构的先验知识。模块最大化模型针对模块识别问题构建了模块最大化优化模型，并利用层次聚类策略实现网络划分，该操作是非常耗时的。……