王 林，閆安文

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

一種改進(jìn)的譜聚類方法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測中的應(yīng)用

王 林，閆安文

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要特征之一。譜聚類方法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測中具有十分重要的作用。針對(duì)譜聚類算法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測中只選擇部分特征向量聚類的問題，提出了一種改進(jìn)的譜聚類方法，該方法對(duì)網(wǎng)絡(luò)矩陣的所有特征向量進(jìn)行加權(quán)，并引入尺度參數(shù)，采用網(wǎng)絡(luò)矩陣的所有特征向量進(jìn)行聚類。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)譜聚類算法相比，該方法可以有效地對(duì)網(wǎng)絡(luò)進(jìn)行劃分，并可以反映出網(wǎng)絡(luò)中社團(tuán)的多尺度特性。

復(fù)雜網(wǎng)絡(luò)；社團(tuán)檢測；模塊度；譜圖方法

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 引言

現(xiàn)實(shí)生活中許多復(fù)雜系統(tǒng)都可以抽象為復(fù)雜網(wǎng)絡(luò)。隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一些共同的拓?fù)涮匦?，如小世界特性、無標(biāo)度特性以及社團(tuán)結(jié)構(gòu)。由于復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)性質(zhì)對(duì)于研究基礎(chǔ)設(shè)施網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、經(jīng)濟(jì)與社會(huì)網(wǎng)絡(luò)具有十分重要的意義[1]，因而受到了國內(nèi)外許多學(xué)者的廣泛關(guān)注。

針對(duì)復(fù)雜網(wǎng)絡(luò)中社團(tuán)的劃分問題，研究者從不同角度出發(fā)，提出了復(fù)雜網(wǎng)絡(luò)中社團(tuán)檢測算法。該算法主要分為三類：基于模塊度的方法[2-4]、基于統(tǒng)計(jì)推理的方法[5]和譜方法[6-8]。從模塊度優(yōu)化問題出發(fā)，NEWMAN M E在文獻(xiàn)[2]中根據(jù)模塊度矩陣的最大特征值所對(duì)應(yīng)的特征向量迭代地將網(wǎng)絡(luò)二分化，直到模塊度取得最大值，模塊度貪婪優(yōu)化算法通過將網(wǎng)絡(luò)中的節(jié)點(diǎn)看作獨(dú)立的社團(tuán)，通過迭代地合并節(jié)點(diǎn)并計(jì)算對(duì)應(yīng)的模塊度，直到模塊度不再取得更大值；從統(tǒng)計(jì)推理的角度出發(fā)，人們發(fā)現(xiàn)可以通過網(wǎng)絡(luò)的結(jié)構(gòu)信息擬合出一個(gè)塊模型，基于此，文獻(xiàn)[5]中提出了用于社團(tuán)檢測的度矯正隨機(jī)塊模型；由于譜聚類算法易于實(shí)現(xiàn)、更加高效并且聚類效果好，因此，許多學(xué)者從譜聚類的角度提出了復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分方法。然而，由于譜聚類算法通常只選擇網(wǎng)絡(luò)矩陣的部分特征向量進(jìn)行聚類，并沒有充分考慮到網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)。

為了改善譜聚類算法在社團(tuán)檢測中的上述缺點(diǎn)，本文提出了一種改進(jìn)的譜聚類方法，該方法通過對(duì)網(wǎng)絡(luò)矩陣的所有特征向量加權(quán)，考慮到了網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)，并引入尺度參數(shù)，還可反映出網(wǎng)絡(luò)中社團(tuán)的多尺度特性。

1 圖傅里葉變換

類似于傳統(tǒng)傅里葉變換積分求和的概念，HAMMOND D K等人[9]將圖Laplace矩陣的特征向量作為頻率分量，Laplace矩陣的特征值作為頻譜，給出了向量圖傅里變換的定義，并引入了譜圖小波變換的概念。

1.1網(wǎng)絡(luò)Laplace矩陣

對(duì)于含有N個(gè)節(jié)點(diǎn)的無向無權(quán)網(wǎng)絡(luò)G=(V,E)，V=(v1,v2,…,vN)為網(wǎng)絡(luò)的節(jié)點(diǎn)集，E為網(wǎng)絡(luò)的邊集。設(shè)網(wǎng)絡(luò)的鄰接矩陣為A，則其元素aij表示為：

(1)

考慮網(wǎng)絡(luò)的無向性，有aij=aji，即矩陣A為實(shí)對(duì)稱矩陣。

設(shè)節(jié)點(diǎn)i的度為d(i)，可以發(fā)現(xiàn):

d(i)=∑jaij

(2)

網(wǎng)絡(luò)Laplace矩陣定義為:L=D-A，其中D=diag(d(1),d(2),…,d(N))為對(duì)角矩陣。Laplace矩陣L為實(shí)對(duì)稱矩陣，其最小特征值λ1=0，該值的重?cái)?shù)為網(wǎng)絡(luò)的連通分支數(shù)，考慮全連通網(wǎng)絡(luò)，其特征值可排列為：0=λ1<λ2≤…≤λN，假設(shè)特征值所對(duì)應(yīng)的特征向量分別為：χ1，χ2，… ，χN，由于矩陣L的實(shí)對(duì)稱特性，對(duì)其特征向量作規(guī)范化處理后，不難發(fā)現(xiàn)不同的特征向量相互正交，并且χ1=(1,1,…,1)T。設(shè)矩陣χ=[χ1,χ2,…,χN]，可以發(fā)現(xiàn)該矩陣的不同列之間相互正交，并且χ與其轉(zhuǎn)置矩陣χT互為逆矩陣，即χχT=χTχ=I,其中I為N階單位矩陣。

1.2網(wǎng)絡(luò)節(jié)點(diǎn)的圖小波表示

2 方法原理

現(xiàn)有的譜聚類方法只選擇網(wǎng)絡(luò)矩陣的部分特征向量進(jìn)行聚類，希望可以采用網(wǎng)絡(luò)的全部特征向量進(jìn)行聚類。如前文所述網(wǎng)絡(luò)Laplace矩陣的零特征值對(duì)應(yīng)的特征向量χ1在所有節(jié)點(diǎn)上的分量均為1，無法將節(jié)點(diǎn)區(qū)分開，而χN又過分地將節(jié)點(diǎn)區(qū)分開(在極端情況下，每個(gè)節(jié)點(diǎn)被劃分為獨(dú)立的社團(tuán))，因此，考慮對(duì)特征向量進(jìn)行加權(quán)，加權(quán)函數(shù)g(x)應(yīng)當(dāng)在χ1上為0，而在較高頻率分量處衰減?？梢哉J(rèn)為網(wǎng)絡(luò)Laplace矩陣的小波基為網(wǎng)絡(luò)節(jié)點(diǎn)在歐式空間中的一種映射，這樣網(wǎng)絡(luò)節(jié)點(diǎn)的聚類問題就可轉(zhuǎn)化為矩陣ψs中行元素的余弦相似性問題。

2.1加權(quán)函數(shù)

為了使加權(quán)函數(shù)具有前文所述性質(zhì)，并能取得較好的局部化效果，采用文獻(xiàn)[10]中明確指定的g(x)定義以及尺度區(qū)間：

(3)

根據(jù)對(duì)應(yīng)的網(wǎng)絡(luò)Laplace矩陣，計(jì)算其最小非零特征值λ2以及最大特征值λN，尺度參數(shù)區(qū)間設(shè)置為：[smin,smax]，其中smin=2/λN，smax=2/λ2。

2.2尺度參數(shù)

不同的網(wǎng)絡(luò)對(duì)應(yīng)的Laplace矩陣不同，為了使加權(quán)函數(shù)能適用于不同的網(wǎng)絡(luò)，引入尺度參數(shù)s，s的值受網(wǎng)絡(luò)Laplace矩陣特征值的約束，這樣，選擇合適的尺度，當(dāng)前網(wǎng)絡(luò)矩陣的特征向量便可取得較好的加權(quán)效果。

當(dāng)尺度參數(shù)s選擇較小值時(shí)，如01)時(shí)，加權(quán)函數(shù)g(sx)則處于壓縮狀態(tài)，只有部分低頻分量被加權(quán)，網(wǎng)絡(luò)劃分的社團(tuán)個(gè)數(shù)較少，節(jié)點(diǎn)的聚類效果則相對(duì)粗糙。實(shí)際上，可以認(rèn)為尺度參數(shù)s反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的連接情況，s值越大，以某節(jié)點(diǎn)為中心，其鄰居節(jié)點(diǎn)越多。s=0.5和s=2時(shí)的加權(quán)函數(shù)曲線如圖1所示。

圖1 加權(quán)函數(shù)g(x) (實(shí)線)，s=0.5時(shí)(點(diǎn)線)，s=2時(shí)(虛線)

3 結(jié)果分析

通過四個(gè)實(shí)際網(wǎng)絡(luò)來測試本文算法：Zachary網(wǎng)絡(luò)[11]，Jazz網(wǎng)絡(luò)[10]，E-mail網(wǎng)絡(luò)[12]，物理學(xué)家(Physicists)合作網(wǎng)絡(luò)[13]。

根據(jù)Zachary網(wǎng)絡(luò)矩陣的最小非零特征值λ2以及最大特征值λN的估計(jì)值，設(shè)置尺度參數(shù)s∈[0.1, 4.2]，當(dāng)尺度參數(shù)s=4.2時(shí)，網(wǎng)絡(luò)被劃分為兩個(gè)社團(tuán)，如圖2所示。

圖2 Zachary網(wǎng)絡(luò)在尺度參數(shù)s=4.2時(shí)的劃分情況

通過設(shè)置不同的尺度參數(shù)，發(fā)現(xiàn)Zachary網(wǎng)絡(luò)在尺度參數(shù)s=4.2時(shí)，網(wǎng)絡(luò)得到了正確劃分。通過設(shè)置不同的尺度參數(shù)，這四個(gè)實(shí)際網(wǎng)絡(luò)的最大模塊度Q值，對(duì)比經(jīng)典社團(tuán)劃分算法：GN算法[2]、CNM算法[4]、DA算法[3]如表1所示。

表1 本文方法與經(jīng)典社團(tuán)劃分算法的Q值對(duì)比

實(shí)驗(yàn)結(jié)果表明，通過選擇合適的尺度參數(shù)以及加權(quán)函數(shù)，復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)能夠得到較好的劃分。

4 結(jié)論

在譜聚類算法的基礎(chǔ)上，本文從譜圖小波變換的角度對(duì)傳統(tǒng)的譜聚類算法進(jìn)行的改進(jìn)：對(duì)網(wǎng)絡(luò)矩陣的所有特征向量進(jìn)行加權(quán)，并利用所有特征向量進(jìn)行聚類，充分考慮了網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)，另外引入了尺度參數(shù)的概念，可以有效地反映網(wǎng)絡(luò)的多尺度特性。由于尺度參數(shù)取離散的對(duì)數(shù)化間隔，是否存在更佳的尺度參數(shù)值以及加權(quán)函數(shù)可使得網(wǎng)絡(luò)得到更優(yōu)的劃分還在研究之中，另外該方法的缺陷在于網(wǎng)絡(luò)矩陣的特征向量的計(jì)算復(fù)雜度較高。

[1] 汪小帆,汪秉宏,曹進(jìn)德,等.復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)功能性質(zhì)及其應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐, 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ìn)的譜聚類方法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測中的應(yīng)用[J].微型機(jī)與應(yīng)用，2017,36(18)：30-31，35.

2017-03-22)

王林(1963-)，男，博士，教授，主要研究方向：復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘、大數(shù)據(jù)分析。

閆安文(1991-)，通信作者，男，碩士，主要研究方向：復(fù)雜網(wǎng)絡(luò)。E-mail：anvinvip@163.com。