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

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

?

譜聚類在社團(tuán)發(fā)現(xiàn)中的應(yīng)用

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

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

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

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

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

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

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

1 網(wǎng)絡(luò)圖與社團(tuán)劃分

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

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

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

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

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

1.2 社團(tuán)的劃分與評價(jià)指標(biāo)

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

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

由上述定義得出，

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

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

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

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

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

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

2 算法描述

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

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

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

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

③ 計(jì)算λ1，λ2，…λk-1對應(yīng)的特征向量u1，u2，…，uk；

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

⑤ 計(jì)算H=D-1/2U；

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

3.2 社團(tuán)質(zhì)量的評價(jià)

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

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

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

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

通過譜聚類對該9個(gè)網(wǎng)絡(luò)劃分社團(tuán)，準(zhǔn)確率如圖6所示.

Zout≤6時(shí)正確率超過90%，因?yàn)闇y試網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)比較明顯；Zout≥7，8時(shí)正確率低于80%，因?yàn)樯鐖F(tuán)沒有明顯社團(tuán)結(jié)構(gòu)了. 應(yīng)用GN模塊度的算法的結(jié)果是Zout≤6時(shí)有90%以上的節(jié)點(diǎn)被正確劃分，與該算法的劃分結(jié)果一致.

4 結(jié)束語

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

[1] 汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[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)絡(luò)重疊社區(qū)發(fā)現(xiàn)的粗糙譜聚類算法[J].小型微型計(jì)算機(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] 蔡曉妍，戴冠中，楊黎斌.基于譜聚類的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].計(jì)算機(jī)科學(xué)，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.

(責(zé)任編輯：劉芳)

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

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

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

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

TP 305

A

1001-0645(2016)07-0701-05

10.15918/j.tbit1001-0645.2016.07.008