譜聚類在社團發(fā)現(xiàn)中的應用

彭靜，廖樂健，翟英，仇晶

(1.河北科技大學 信息科學與工程學院，河北，石家莊 050018；2.北京理工大學 計算機學院，北京 100081；3.河北經(jīng)貿(mào)大學 信息技術(shù)學院，河北，石家莊 050061)

?

譜聚類在社團發(fā)現(xiàn)中的應用

彭靜1，廖樂健2，翟英3，仇晶1

(1.河北科技大學 信息科學與工程學院，河北，石家莊 050018；2.北京理工大學 計算機學院，北京 100081；3.河北經(jīng)貿(mào)大學 信息技術(shù)學院，河北，石家莊 050061)

在分析譜聚類原理的基礎上，研究了其在社團發(fā)現(xiàn)中的應用，提出了快速估計社團數(shù)量的新方法. 該方法通過計算和分析Laplacian矩陣特征值的分布來估計社團的數(shù)量，利用K-means算法對Laplacian矩陣特征向量構(gòu)造的向量空間進行聚類，實現(xiàn)社團的發(fā)現(xiàn). 該算法在真實社會網(wǎng)絡和合成網(wǎng)絡上做了測試，驗證了在社團發(fā)現(xiàn)中的準確性和有效性.

Laplacian矩陣；譜聚類；K-means算法；社團發(fā)現(xiàn)

社會網(wǎng)絡是一群人或團體按某種關系連接在一起構(gòu)成的一個系統(tǒng)[1]. 人與人之間關系如朋友、同事、同學等，這種關系用圖來表示，圖中節(jié)點表示個體，節(jié)點之間的邊表示個體間的關系. 社團是指整個網(wǎng)絡由若干個組構(gòu)成，組內(nèi)節(jié)點間的連接比較緊密，而組間節(jié)點連接比較松散[2]，發(fā)現(xiàn)網(wǎng)絡中的社團結(jié)構(gòu)并對其進行分析是了解整個網(wǎng)絡結(jié)構(gòu)、特征和功能的重要途徑[3]. 圖1表示一個有8個節(jié)點分為兩個社團的網(wǎng)絡.

對于所劃分社團的質(zhì)量，一般采用Girvan和Newman提出的模塊度[4]來度量，把劃分社團后的網(wǎng)絡和相應的零模型比較. 但是，當社區(qū)大小差異較大時，模塊度方法并不能得到所期望的值[5]. 傳導率[6](conductance)是Jaewon Yang提出的評價社團質(zhì)量函數(shù)，該函數(shù)在230個已知社團結(jié)構(gòu)的大規(guī)模網(wǎng)絡中經(jīng)過驗證，魯棒性和敏感性最好.

本文依據(jù)傳導率函數(shù)定義和譜聚類基本原理，提出分析圖的矩陣譜分布估計社團數(shù)量的方法，在確定社團數(shù)量前提下，利用K-means算法聚類劃分社團. 并給出了在真實網(wǎng)絡和合成網(wǎng)絡上測試結(jié)果.

1 網(wǎng)絡圖與社團劃分

1.1 網(wǎng)絡圖的表示

網(wǎng)絡用圖來表示，圖G=(V，E)是一個節(jié)點數(shù)為n、邊數(shù)為m的簡單圖(沒有重邊和自環(huán))，G的節(jié)點集合為V={v1，v2，…，vn}，節(jié)點數(shù)n=|V|，邊數(shù)m=|E|. 表示圖G的鄰接矩陣A=(aij)n×n是一個n階方陣，G是無權(quán)圖，第i行j列的元素aij定義為

在圖論中，圖的Laplacian矩陣用L表示，定義為L=D-A，規(guī)范化矩陣L得到Lsym，Lsym=D-1/2LD-1/2，Lsym是對稱(symmetric)矩陣，其特征譜刻畫了圖的拓撲結(jié)構(gòu)特征，Lsym有兩個重要性質(zhì)[7].

性質(zhì)1 對任意向量f∈n滿足公式：

性質(zhì)2 Lsym的特征值是非負實數(shù)，從小到大排序，記為0=λ0≤λ1≤…≤λn-1.

1.2 社團的劃分與評價指標

在社會網(wǎng)絡中，社團的大小和數(shù)量是不確定的，社團劃分的質(zhì)量評價是一個難題. Jaewon Yang[6]定義了13個社團評價函數(shù)，在230個已知社團結(jié)構(gòu)的大規(guī)模的真實網(wǎng)絡測試，其中傳導率(Conductance)函數(shù)在魯棒性、敏感性方面表現(xiàn)最好，本文從傳導率函數(shù)入手依據(jù)譜聚類的基本原理得出社團劃分的方法.

即S內(nèi)的節(jié)點與S外節(jié)點之間連邊數(shù)與S內(nèi)的節(jié)點度的和的比值，f(s)值越小，社團S的質(zhì)量越高.

由上述定義得出，

為了最小化f(s)，根據(jù)1.1性質(zhì)1，定義一個指示向量hj=[h1jh2j… hnj]′，

構(gòu)造矩陣H，k個指示向量作為矩陣的列，可以計算出：

由T和H定義可知，H=D-1/2T，H是n×k的指示矩陣，根據(jù)譜聚類的基本原理，通過對H的行聚類[9]就得到k個節(jié)點集合：S1，S2…，Sk.

1.3 社團數(shù)量的確定

社團數(shù)量的確定在社團發(fā)現(xiàn)中一個難點，k值如何確定呢？根據(jù)1.2的結(jié)論，Tr(T′LsymT)>0，T的k列分別對應矩陣Lsym的前k個特征值對應的特征向量，根據(jù)1.1性質(zhì)2，Lsym有n個特征值為：0=λ0≤λ1≤…≤λn-1. λ0=0說明圖G是連通圖，取k=1，Lsym次小特征值λ1對應的特征向量作為T的一列，T∈n×k，由于特征向量的分量是正交的，特征向量的元素分為正負兩部分，正元素所對應的節(jié)點是一個社團，負元素所對應的節(jié)點是另一個社團. 因此應用Lsym的次小特征值對應的特征向量進行對圖進行二分，這就是常用的譜平分法，因此如果分為多個社團，就多次重復該算法，但通常情況下無法知道社團的數(shù)量.

通過分析Lsym的特征值分布，采用基于距離的啟發(fā)式方法，取數(shù)值變化比較平緩的前k個較小特征值，比如，發(fā)現(xiàn)第1～m的特征值都比較小，到了m+1突然變成較大的數(shù)，那么就可以選擇k=m. 對應的特征向量構(gòu)造矩陣T，T∈n×k，計算H=D-1/2T，得到指示矩陣H，H∈n×k.

2 算法描述

根據(jù)1.3的結(jié)論，計算圖G的Lsym，求出Lsym的特征值，按從小到大排序，找到k個較小特征值和對應的特征向量，構(gòu)造矩陣T，T∈n×k，計算H=D-1/2T，H的n行對應n個節(jié)點的k個屬性，通過k-means算法計算n個的節(jié)點的k個聚類，進而發(fā)現(xiàn)k個社團.

輸入：圖G的鄰接矩陣A=(aij)n×n，聚類的數(shù)量k.

① 計算G的規(guī)范化拉普拉斯矩陣Lsym；

② 計算Lsym的特征值并排序，0=λ1≤λ2≤…≤λn；

③ 計算λ1，λ2，…λk-1對應的特征向量u1，u2，…，uk；

④ 以特征向量u1，u2，…，uk為列構(gòu)造n×k矩陣U；

⑤ 計算H=D-1/2U；

⑥ i=1，2，…，n，令向量yi∈k為矩陣H的第i行，應用K-means算法對(yi)i=1，2，…，n聚類，分別為C1，C2，…，Ck.

輸出：節(jié)點集合S1，S2，…，Sk，Si={j|yj∈Ci}.

3 實驗結(jié)果

3.1 Zachary空手道俱樂部網(wǎng)絡

是一次行業(yè)峰會，李若認識了邵南。她10厘米高的鞋跟卡在了電梯的門縫里，穿著超短裙的她也不好意思低下身子去拔鞋，一電梯的人都停在那里，是邵南幫她拿了出來，這并不足以讓她感動，感動的是當他用手托著那雙鞋輕輕地給她穿上的時候，李若有了石破天驚的感覺，她覺得自己真的成了灰姑娘，那一雙GUCCI鞋成就了她。

Zachary空手道俱樂部網(wǎng)絡[10](Zachary’skarateclubnetwork)是驗證社團劃分算法常用的“基準網(wǎng)絡”，從1970～1972年，Zachary通過3年時間觀察了美國一所大學空手道俱樂部成員間的社會關系，構(gòu)造出了含有34個節(jié)點和78條邊的網(wǎng)絡，每一個節(jié)點表示俱樂部的一個成員，節(jié)點之間的連接表示兩個成員經(jīng)常出現(xiàn)在俱樂部活動之外的其他場合. 在Zachary研究這個俱樂部成員社會關系期間，由于教練Hi(節(jié)點0)和俱樂部主管John(節(jié)點33)之間意見分歧，該社會網(wǎng)絡分裂成兩個分別以教練Hi(節(jié)點0)和主管John(節(jié)點33)為核心的兩個社團.

分析該網(wǎng)絡的Lsym的特征值分布如圖2所示，可以看到有4個較小特征值.

分別取分別選擇k=2，3，4時的聚類結(jié)果分別如圖3所示.

k=2時檢測結(jié)果和實際相符，k=3和k=4時，檢測到了較小規(guī)模的社團，說明大社團中存在更小的社團，與傳統(tǒng)模塊度的檢測方法得到的社團結(jié)果相同.

3.2 社團質(zhì)量的評價

使用傳導率來衡量社團劃分的結(jié)果，聚類結(jié)果中平均傳導率如圖4所示，f(s)越小，社團結(jié)構(gòu)越明顯.

為了驗證劃分社團結(jié)果的準確性，利用譜聚類算法計算k=2～10的社團劃分，計算每個劃分結(jié)果的傳導率的平均值，k=2時，傳導率值最小，表明發(fā)現(xiàn)的是兩個核心社團，k=3、4傳導率值平緩增加，可以理解為除了這兩個核心社團之外存在兩個小的社團.k的取值從4到5，傳導率均值有較高的突變，k≥5時f(s)的值趨于穩(wěn)定，表明沒有新的社團. 因此可以認為k取值為4是比較合理的，驗證了估計社團數(shù)目的正確性.

實驗中還使用計算機生成了9個網(wǎng)絡，該網(wǎng)絡是Girvan與Newman提出的均質(zhì)社團結(jié)構(gòu)測試網(wǎng)絡[11-12](GN合成網(wǎng)絡)，該網(wǎng)絡含有128個節(jié)點，4個社團，每個社團的節(jié)點數(shù)為32. 在該網(wǎng)絡中，同一個社團的2個節(jié)點以概率Pin隨機連邊，不屬于同一社團的2個節(jié)點以概率Pout連邊.Zin為節(jié)點與社團內(nèi)部節(jié)點連邊數(shù)目的期望值，Zout為節(jié)點與社團外節(jié)點連邊數(shù)目的期望值，Pin和Pout的取值，保證2個節(jié)點的度期望值為16，即Zin+Zout=16.Zout取值從0～8分別生成9個網(wǎng)絡，Lsym的特征值分布如圖5所示.

已知測試網(wǎng)絡的社團為4，λ0=0.Zout從0～8，λ1，λ2，λ3的值逐漸增加，Zout=7、8的時，λ1，λ2，λ3接近λ4，說明社團的結(jié)構(gòu)不再明顯.Zout=0時，λ1=λ2=λ3=0，網(wǎng)絡有4個社團，社團之間沒有連接；Zout=1，2，3，4時，λ1，λ2，λ3較小，距離較近，隨著Zout增大，λ3，λ4的值在逐漸增大；Zout=7，8時λ1，λ2，λ3的值接近λ4，網(wǎng)絡沒有明顯的社團結(jié)構(gòu)，驗證了k值選擇方法是正確的.

通過譜聚類對該9個網(wǎng)絡劃分社團，準確率如圖6所示.

Zout≤6時正確率超過90%，因為測試網(wǎng)絡的社團結(jié)構(gòu)比較明顯；Zout≥7，8時正確率低于80%，因為社團沒有明顯社團結(jié)構(gòu)了. 應用GN模塊度的算法的結(jié)果是Zout≤6時有90%以上的節(jié)點被正確劃分，與該算法的劃分結(jié)果一致.

4 結(jié)束語

通過分析評價社團劃分質(zhì)量的傳導率函數(shù)的定義，依據(jù)譜聚類的基本原理，研究了譜聚類在社團發(fā)現(xiàn)中的應用，提出了根據(jù)Laplacian矩陣特征值的分布快速估計社團數(shù)量的方法. 通過Laplacian矩陣特征向量構(gòu)造向量空間，應用K-means算法聚類發(fā)現(xiàn)社團，在真實的社會網(wǎng)絡中應用傳導率函數(shù)驗證了該算法是有效的，在GN合成網(wǎng)絡中用準確率驗證了該算法的正確性.

[1] 汪小帆，李翔，陳關榮.網(wǎng)絡科學導論[M].北京：高等教育出版社，2012.

Wang Xiaofan，Li Xiang，Chen Guanrong. Network science: an introduction[M]. Beijing: Higher Education Press，2012. (in Chinese)

[2] Girvan M，Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences，2002，99(12):7821-7826.

[3] Ng A Y，Jordan M I，Weiss Y. On spectral clustering: Analysis and an algorithm[J]. Advances in Neural Information Processing Systems，2002，2:849-856.

[4] 黃發(fā)良，肖南峰.用于網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)的粗糙譜聚類算法[J].小型微型計算機系統(tǒng)，2012，2:263-266.

Huang Faliang，Xiao Nanfeng. Rough spectral clustering algorithm applied to overlapping network communities discovery[J]. Journal of Chinese Computer Systems，2012，2:263-266. (in Chinese)

[5] 蔡曉妍，戴冠中，楊黎斌.基于譜聚類的復雜網(wǎng)絡社團發(fā)現(xiàn)算法[J].計算機科學，2009，9:49-50.

Cai Xiaoyan，Dai Guanzhong，Yang Libin. Community-finding algorithm in complex networks based on spectral clustering[J]. Computer Science，2009，9:49-50. (in Chinese)

[6] Yang J，Leskovec J. Defining and evaluating network communities based on ground-truth[C]∥Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. [S.l.]: ACM，2012:3.

[7] Sole-Ribalta A，De Domenico M，Kouvaris N E，et al. Spectral properties of the Laplacian of multiplex networks[J]. Physical Review E，2013，88(3):032807.

[8] Gu M，Zha H，Ding C，et al. Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering[R]. Philadelphia, USA: University of Pennsylvania，2001.

[9] Bach F R，Jordan M I. Learning spectral clustering，with application to speech separation[J]. The Journal of Machine Learning Research，2006，7:1963-2001.

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

[11] Malliaros F D，Vazirgiannis M. Advanced graph mining for community evaluation in social networks and the web[C]∥Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. [S.l.]: ACM，2013:771-772.

[12] Newman M E J. Spectral methods for community detection and graph partitioning[J]. Physical Review E，2013，88(4):042822.

(責任編輯：劉芳)

Spectral Clustering for Community Detection

PENG Jing1，LIAO Le-jian2，ZHAI Ying3，QIU Jing1

(1.School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang, Hebei 050018，China; 2.School of Computer Science，Beijing Institute of Technology，Beijing 100081，China; 3.School of Information and Technology，Hebei University of Economics and Business，Shijiazhang, Hebei 050061，China)

In this paper spectral clustering was applied to detect the community in social network，and a new method was proposed to estimate the number of communities. According to this new method，the number of communities was estimated by calculating and analyzing the eigenvalues distribution of Laplacian matrix. K-means algorithm was used to clustering vector space which was constructed by eigenvectors of Laplacian matrix. The method was tested on a range of examples，including real-world and synthetic networks. Experimental results show that the method for community detection is accurate and effective.

Laplacian matrix; spectral clustering; K-means algorithm; community detection

2014-12-10

國家“九七三”計劃項目(2013CB329605)；國家自然科學基金資助項目(61300120)；河北省自然科學基金資助項目(F2012208016)；河北省教育廳資助項目(YQ2013032)

彭靜(1970—)，女，副教授，E-mail:pengjing70@163.com.

廖樂健(1962—)，男，教授，博士生導師，E-mail:liaolj@bit.edu.cn.

TP 305

A

1001-0645(2016)07-0701-05

10.15918/j.tbit1001-0645.2016.07.008