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

王 林，闫安文

(西安理工大学 自动化与信息工程学院，陕西 西安 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]中根据模块度矩阵的最大特征值所对应的特征向量迭代地将网络二分化，直到模块度取得最大值，模块度贪婪优化算法通过将网络中的节点看作独立的社团，通过迭代地合并节点并计算对应的模块度，直到模块度不再取得更大值；从统计推理的角度出发，人们发现可以通过网络的结构信息拟合出一个块模型，基于此，文献[5]中提出了用于社团检测的度矫正随机块模型；由于谱聚类算法易于实现、更加高效并且聚类效果好，因此，许多学者从谱聚类的角度提出了复杂网络社团划分方法。然而，由于谱聚类算法通常只选择网络矩阵的部分特征向量进行聚类，并没有充分考虑到网络的全局拓扑结构。

为了改善谱聚类算法在社团检测中的上述缺点，本文提出了一种改进的谱聚类方法，该方法通过对网络矩阵的所有特征向量加权，考虑到了网络的全局拓扑结构，并引入尺度参数，还可反映出网络中社团的多尺度特性。

1 图傅里叶变换

类似于传统傅里叶变换积分求和的概念，HAMMOND D K等人[9]将图Laplace矩阵的特征向量作为频率分量，Laplace矩阵的特征值作为频谱，给出了向量图傅里变换的定义，并引入了谱图小波变换的概念。

1.1网络Laplace矩阵

对于含有N个节点的无向无权网络G=(V,E)，V=(v1,v2,…,vN)为网络的节点集，E为网络的边集。设网络的邻接矩阵为A，则其元素aij表示为：

(1)

考虑网络的无向性，有aij=aji，即矩阵A为实对称矩阵。

设节点i的度为d(i)，可以发现:

d(i)=∑jaij

(2)

网络Laplace矩阵定义为:L=D-A，其中D=diag(d(1),d(2),…,d(N))为对角矩阵。Laplace矩阵L为实对称矩阵，其最小特征值λ1=0，该值的重数为网络的连通分支数，考虑全连通网络，其特征值可排列为：0=λ1<λ2≤…≤λN，假设特征值所对应的特征向量分别为：χ1，χ2，… ，χN，由于矩阵L的实对称特性，对其特征向量作规范化处理后，不难发现不同的特征向量相互正交，并且χ1=(1,1,…,1)T。设矩阵χ=[χ1,χ2,…,χN]，可以发现该矩阵的不同列之间相互正交，并且χ与其转置矩阵χT互为逆矩阵，即χχT=χTχ=I,其中I为N阶单位矩阵。

1.2网络节点的图小波表示

2 方法原理

现有的谱聚类方法只选择网络矩阵的部分特征向量进行聚类，希望可以采用网络的全部特征向量进行聚类。如前文所述网络Laplace矩阵的零特征值对应的特征向量χ1在所有节点上的分量均为1，无法将节点区分开，而χN又过分地将节点区分开(在极端情况下，每个节点被划分为独立的社团)，因此，考虑对特征向量进行加权，加权函数g(x)应当在χ1上为0，而在较高频率分量处衰减。可以认为网络Laplace矩阵的小波基为网络节点在欧式空间中的一种映射，这样网络节点的聚类问题就可转化为矩阵ψs中行元素的余弦相似性问题。

2.1加权函数

为了使加权函数具有前文所述性质，并能取得较好的局部化效果，采用文献[10]中明确指定的g(x)定义以及尺度区间：

(3)

根据对应的网络Laplace矩阵，计算其最小非零特征值λ2以及最大特征值λN，尺度参数区间设置为：[smin,smax]，其中smin=2/λN，smax=2/λ2。

2.2尺度参数

不同的网络对应的Laplace矩阵不同，为了使加权函数能适用于不同的网络，引入尺度参数s，s的值受网络Laplace矩阵特征值的约束，这样，选择合适的尺度，当前网络矩阵的特征向量便可取得较好的加权效果。

当尺度参数s选择较小值时，如01)时，加权函数g(sx)则处于压缩状态，只有部分低频分量被加权，网络划分的社团个数较少，节点的聚类效果则相对粗糙。实际上，可以认为尺度参数s反映了网络中节点的连接情况，s值越大，以某节点为中心，其邻居节点越多。s=0.5和s=2时的加权函数曲线如图1所示。

图1 加权函数g(x) (实线)，s=0.5时(点线)，s=2时(虚线)

3 结果分析

通过四个实际网络来测试本文算法：Zachary网络[11]，Jazz网络[10]，E-mail网络[12]，物理学家(Physicists)合作网络[13]。

根据Zachary网络矩阵的最小非零特征值λ2以及最大特征值λN的估计值，设置尺度参数s∈[0.1, 4.2]，当尺度参数s=4.2时，网络被划分为两个社团，如图2所示。

图2 Zachary网络在尺度参数s=4.2时的划分情况

通过设置不同的尺度参数，发现Zachary网络在尺度参数s=4.2时，网络得到了正确划分。通过设置不同的尺度参数，这四个实际网络的最大模块度Q值，对比经典社团划分算法：GN算法[2]、CNM算法[4]、DA算法[3]如表1所示。

表1 本文方法与经典社团划分算法的Q值对比

实验结果表明，通过选择合适的尺度参数以及加权函数，复杂网络中的社团结构能够得到较好的划分。

4 结论

在谱聚类算法的基础上，本文从谱图小波变换的角度对传统的谱聚类算法进行的改进：对网络矩阵的所有特征向量进行加权，并利用所有特征向量进行聚类，充分考虑了网络的全局拓扑结构，另外引入了尺度参数的概念，可以有效地反映网络的多尺度特性。由于尺度参数取离散的对数化间隔，是否存在更佳的尺度参数值以及加权函数可使得网络得到更优的划分还在研究之中，另外该方法的缺陷在于网络矩阵的特征向量的计算复杂度较高。

[1] 汪小帆,汪秉宏,曹进德,等.复杂网络的结构功能性质及其应用[J].系统工程理论与实践, 2008,28(5): 45-48.

[2] NEWMAN M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(103):8577-82.

[3] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2005, 72(2):986-1023.

[4] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2010, 70(6 Pt 2):264-277.

[5] KARRER B, NEWMAN M E J. Stochastic blockmodels and community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011,83(1pt2): 016107.

[6] WHITE S, SMYTH P. A spectral clustering approach to finding communities in graph[C]. Siam International Conference on Data Mining, 2005: 274-285.

[7] NEWMAN M E. Spectral methods for community detection and graph partitioning.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2013, 88(4):330-337.

[8] Shen Huawei, Cheng Xueqi. Spectral methods for the detection of network community structure: a comparative analysis[J]. Computer Science, 2010,2010(10):10020.

[9] HAMMOND D K, VANDERGHEYNST P, GRIBONVAL R. Wavelets on graphs via spectral graph theory[J]. Applied & Computational Harmonic Analysis, 2009, 30(2):129-150.

[10] GLEISER P, DANON L. Community structure in Jazz[J]. Advances in Complex Systems, 2003(6): 565-573.

[11] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.

[12] EBEL H, MIELSCH L I, BORNHOLDT S. Scale-free topology of e-mail networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2002, 66(3):035103.

[13] NEWMAN M E J. The structure of scientific collaboration networks[C]. Proceedings of the National Academy of Sciences of the United States of America, 2001, 98(2):404-409.

An improved spectral clusteringmethod used in community detection of complex network

Wang Lin, Yan Anwen

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

TN929.12

A

10.19358/j.issn.1674- 7720.2017.18.009

王林，闫安文.一种改进的谱聚类方法在复杂网络社团检测中的应用[J].微型机与应用，2017,36(18)：30-31，35.

2017-03-22)

王林(1963-)，男，博士，教授，主要研究方向：复杂网络、数据挖掘、大数据分析。

闫安文(1991-)，通信作者，男，硕士，主要研究方向：复杂网络。E-mail：anvinvip@163.com。