王 林，闫安文

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

一种改进的谱聚类方法在复杂网络社团检测中的应用

王 林，闫安文

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

社团结构是复杂网络的重要特征之一。谱聚类方法在复杂网络社团检测中具有十分重要的作用。针对谱聚类算法在复杂网络社团检测中只选择部分特征向量聚类的问题，提出了一种改进的谱聚类方法，该方法对网络矩阵的所有特征向量进行加权，并引入尺度参数，采用网络矩阵的所有特征向量进行聚类。实验结果表明，与传统谱聚类算法相比，该方法可以有效地对网络进行划分，并可以反映出网络中社团的多尺度特性。

复杂网络；社团检测；模块度；谱图方法

Abstract: Community structure is one of important features of complex network. Spectral clustering methods take important position in the community detection in complex networks. Aiming at the issue that just a part of eigenvectors are used to cluster in the community detection, an improved spectral clustering method is proposed, in which all eigenvectors are weighted, scale parameter is involved and all eigenvectors are used to cluster. Experiment results indicate that, compared with traditional spectral clustering methods, not only community structures can be efficiently detected, but multi-scale feature of community can be reflected.

Key words:complex network; community detection; modularity; spectral graph method

0 引言

现实生活中许多复杂系统都可以抽象为复杂网络。随着对复杂网络的深入研究，人们发现许多实际网络都具有一些共同的拓扑特性，如小世界特性、无标度特性以及社团结构。由于复杂网络的社团结构性质对于研究基础设施网络、生物网络、经济与社会网络具有十分重要的意义[1]，因而受到了国内外许多学者的广泛关注。

针对复杂网络中社团的划分问题，研究者从不同角度出发，提出了复杂网络中社团检测算法。该算法主要分为三类：基于模块度的方法[2-4]、基于统计推理的方法[5]和谱方法[6-8]。从模块度优化问题出发，NEWMAN M E在文献[2]中根据模块度矩阵的最大特征值所对应的特征向量迭代地将网络二分化，直到模块度取得最大值，模块度贪婪优化算法通过将网络中的节点看作独立的社团，通过迭代地合并节点并计算对应的模块度，直到模块度不再取得更大值；……