基于多重特征向量的有向網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法

楊　凱，郭　強，劉曉露，劉建國,2

(1. 上海理工大學復雜系統(tǒng)科學研究中心　上海 楊浦區(qū)　200093;　2. 上海財經(jīng)大學科研實驗中心　上海 楊浦區(qū)　200433)

基于多重特征向量的有向網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法

楊凱1，郭強1，劉曉露1，劉建國1,2

(1. 上海理工大學復雜系統(tǒng)科學研究中心上海 楊浦區(qū)200093;2. 上海財經(jīng)大學科研實驗中心上海 楊浦區(qū)200433)

有向網(wǎng)絡(luò)社團結(jié)構(gòu)的識別對于理解復雜系統(tǒng)的結(jié)構(gòu)特性和動力學特性都有著重要的意義。提出了一種基于拉普拉斯矩陣多重特征向量的有向網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法，該算法利用有向網(wǎng)絡(luò)拉普拉斯矩陣的前c個較小特征值所對應(yīng)的特征向量來劃分有向網(wǎng)絡(luò)的社團結(jié)構(gòu)。在人工數(shù)據(jù)和實證數(shù)據(jù)上與模塊度的譜優(yōu)化算法和模擬退火算法做了對比實驗。實驗結(jié)果表明，當社團結(jié)構(gòu)明顯時，該算法的歸一化互信息指標的值接近于1。當社團結(jié)構(gòu)不明顯時，該算法所取得的效果也優(yōu)于譜優(yōu)化和模擬退火算法。與這兩種算法相比，在實證網(wǎng)絡(luò)上模塊度Q值也可以提高17.28% 和19.21%。該文工作對于理解有向網(wǎng)絡(luò)上拉普拉斯矩陣的多重特征向量與網(wǎng)絡(luò)的社團結(jié)構(gòu)的關(guān)系具有十分重要的意義。

社團結(jié)構(gòu);有向網(wǎng)絡(luò);拉普拉斯矩陣;譜聚類

1　研究背景介紹

現(xiàn)實世界中許多復雜系統(tǒng)都可以用網(wǎng)絡(luò)[1]來刻畫與描述，如社會網(wǎng)絡(luò)[2]、信息和技術(shù)網(wǎng)絡(luò)[3]及生物網(wǎng)絡(luò)[4]等。這些網(wǎng)絡(luò)大都為有向網(wǎng)絡(luò)，并且通常呈現(xiàn)出明顯的社團結(jié)構(gòu)。探索有向網(wǎng)絡(luò)的社團結(jié)構(gòu)[5-9]對于理解網(wǎng)絡(luò)的結(jié)構(gòu)[10-11]和其所代表系統(tǒng)的動力學機制有著重要的意義。近年來，很多研究學者提出了不同的算法[12-15]探索有向網(wǎng)絡(luò)的社團結(jié)構(gòu)。其中一個重要并且廣泛應(yīng)用的算法為譜聚類算法[16-19]。該方法利用一個能表示數(shù)據(jù)集特征矩陣的譜信息劃分無向網(wǎng)絡(luò)的社團結(jié)構(gòu)。這些矩陣包括鄰接矩陣[20]、模塊度矩陣[15]和拉普拉斯矩陣(包括標準的拉普拉斯矩陣[21]和規(guī)范的拉普拉斯矩陣[22])等。文獻[23]比較了這些不同矩陣在社團結(jié)構(gòu)探測中的效果，發(fā)現(xiàn)利用規(guī)范拉普拉斯矩陣的譜聚類算法所劃分的社團結(jié)構(gòu)效果最優(yōu)，說明利用譜聚類劃分社團結(jié)構(gòu)時考慮節(jié)點度的異質(zhì)分布特性是很重要的。根據(jù)在不同無向網(wǎng)絡(luò)上拉普拉斯矩陣的基本性質(zhì)，文獻[24]提出了通用的譜聚類算法，總結(jié)了在無向網(wǎng)絡(luò)上如何利用拉普拉斯矩陣劃分社團結(jié)構(gòu)。而對于有向網(wǎng)絡(luò)，文獻[25]基于隨機游走過程提出了強連通有向網(wǎng)絡(luò)的拉普拉斯矩陣，推導了其在有向網(wǎng)絡(luò)中的性質(zhì)及其在網(wǎng)絡(luò)分割中的作用。這些工作為利用拉普拉斯矩陣對有向網(wǎng)絡(luò)社團劃分提供了理論基礎(chǔ)?；谖墨I[25]的理論，文獻[26]提出了有向網(wǎng)絡(luò)拉普拉斯矩陣的擴展形式，用分層有向網(wǎng)絡(luò)譜分割算法對網(wǎng)絡(luò)社團結(jié)構(gòu)進行劃分。該方法僅僅基于拉普拉斯矩陣次小特征值所對應(yīng)的特征向量進行社團結(jié)構(gòu)劃分。然而，拉普拉斯矩陣的其他特征向量也包含了社團結(jié)構(gòu)的信息。圖1給出了一個包含128個節(jié)點，c=6個社團結(jié)構(gòu)(分別記為為網(wǎng)絡(luò)中實際存在的社團結(jié)構(gòu)的個數(shù))的人工網(wǎng)絡(luò)[27]上拉普拉斯矩陣前6個較小的特征值所對應(yīng)的特征向量。從圖1b可以發(fā)現(xiàn)節(jié)點編號從84～ 110的特征分量明顯跟其他特征分量的值差距較大，即網(wǎng)絡(luò)中的社團結(jié)構(gòu)C5可以由第2個特征向量的特征分量體現(xiàn)。同理，從圖中可知拉普拉斯矩陣前c個較小特征值所對應(yīng)的特征向量都包含了社團結(jié)構(gòu)信息，這些特征向量對應(yīng)節(jié)點上的分量反映了網(wǎng)絡(luò)中真實社團結(jié)構(gòu)(圖中虛線分割部分)。

圖1 人工網(wǎng)絡(luò)上拉普拉斯矩陣L的前6個較小特征值所對應(yīng)的特征向量xi(i=1,2,…,6)。其中，Ci( i=1,2,…,6)表示社團結(jié)構(gòu)的標號

基于上述思想，本文利用多個拉普拉斯矩陣的特征向量(multiple eigenvectors of Laplacian,MEL)識別有向網(wǎng)絡(luò)的社團結(jié)構(gòu)。首先，給出了有向網(wǎng)絡(luò)拉普拉斯矩陣的形式。然后，針對不同情況下的有向網(wǎng)絡(luò)修正了轉(zhuǎn)移概率矩陣使其具有唯一的穩(wěn)態(tài)分布，詳細描述了MEL算法的步驟。最后，通過實驗將該算法與模塊度的譜優(yōu)化算法[15](spectral optimization method,SOM)和模擬退火算法[28](simulated annealing,SA)做了對比分析。實驗結(jié)果表明本文的算法能更加準確地探索有向網(wǎng)絡(luò)的社團結(jié)構(gòu)。

2　理論基礎(chǔ)與方法

如果有向網(wǎng)絡(luò)G是強連通網(wǎng)絡(luò)(即網(wǎng)絡(luò)中任意兩個節(jié)點都能相互到達)，那么根據(jù)Perron-Frobenius定理[30]可知轉(zhuǎn)移概率矩陣P至少有一個左特征向量，它所對應(yīng)的特征值為1。如果轉(zhuǎn)移概率矩陣P有唯一一個特征值為1，那么網(wǎng)絡(luò)G是非周期的。為了探索網(wǎng)絡(luò)G的社團結(jié)構(gòu)，分情況討論。

首先，假定網(wǎng)絡(luò)G是強連通并且是非周期的，則對應(yīng)的轉(zhuǎn)移概率矩陣P有唯一的左特征向量π滿足：πP=π，其中特征向量π為隨機游走的穩(wěn)態(tài)分布。定義對角矩陣Π對角線元素的值為π的每個分量，即。那么，有向網(wǎng)絡(luò)的拉普拉斯矩陣L有如下形式：

式中，矩陣I為單位矩陣。

最后，如果網(wǎng)絡(luò)G不是強連通的,本文引入PageRank轉(zhuǎn)移概率矩陣PPR：

式中，向量e為n維的單位向量；1?α是網(wǎng)絡(luò)中的節(jié)點隨機轉(zhuǎn)移到任意節(jié)點的概率，本文設(shè)α=0.99。當網(wǎng)絡(luò)不是強連通網(wǎng)絡(luò)時，用PPR代替P，再計算該網(wǎng)絡(luò)的拉普拉斯矩陣。

通過上面的轉(zhuǎn)化，可以得到不同情況下有向網(wǎng)絡(luò)G的拉普拉斯矩陣形式，從而利用拉普拉斯矩陣前c個特征值對應(yīng)的特征向量進行社團劃分。

2.2MEL算法描述

利用拉普拉斯矩陣的多個特征向量所包含的社團結(jié)構(gòu)信息，本文提出了基于拉普拉斯矩陣多重特征向量劃分社團結(jié)構(gòu)的算法，算法具體步驟描述如下。

2)根據(jù)矩陣P特征值1的個數(shù)判斷網(wǎng)絡(luò)G的類型,下面分3種情況討論：

③ 如果網(wǎng)絡(luò)G不是強連通，有：

3)計算轉(zhuǎn)移概率的穩(wěn)態(tài)分布π：πP′=π。

4)計算網(wǎng)絡(luò)G的拉普拉斯矩陣：

5)計算拉普拉斯矩陣的特征值λ及其對應(yīng)的特征向量矩陣X：LX=λX。

6)對特征值從小到大進行排序取前c個特征值所對應(yīng)的特征向量，這里c為網(wǎng)絡(luò)中社團結(jié)構(gòu)的個數(shù)。對矩陣 ′X用k-means算法聚類得到每個節(jié)點的社團結(jié)構(gòu)標號矩陣M。

2.3評價指標

本文采用歸一化互信息[31-32](normalized mutual information,NMI)來評價算法對網(wǎng)絡(luò)社團結(jié)構(gòu)劃分的準確性。NMI計算公式如下：

式中，M1是網(wǎng)絡(luò)的真實的社團結(jié)構(gòu)；M2是用算法得到的社團結(jié)構(gòu)；Nc是社團結(jié)構(gòu)的數(shù)量；n是網(wǎng)絡(luò)的節(jié)點數(shù)；nst表示真實社團s中的節(jié)點劃分在算法得到的社團t中的數(shù)量；表示在真實社團結(jié)構(gòu)s中節(jié)點的數(shù)量；表示在算法得到的社團t中節(jié)點的數(shù)量。對于該評價標準，如果算法劃分所得到的社團結(jié)構(gòu)與網(wǎng)絡(luò)中真實存在的社團結(jié)構(gòu)完全一致的話，則NMI取最大值1；而當劃分結(jié)果最差，即劃分出來的社團結(jié)構(gòu)與網(wǎng)絡(luò)中真實存在的社團結(jié)構(gòu)完全不一樣，也就說二者沒有重疊，這時NMI取最小值0。

使用NMI指標評價社團結(jié)構(gòu)算法性能時必須知道網(wǎng)絡(luò)的真實社團結(jié)構(gòu)信息，對于網(wǎng)絡(luò)社團結(jié)構(gòu)信息未知的這種情況，采用模塊度指標Q來衡量算法的優(yōu)劣。模塊度[33]是用于刻畫社團特性強弱的參數(shù)，是應(yīng)用廣泛的評判社團結(jié)構(gòu)強弱的指標。文獻[15]將其擴展到了有向網(wǎng)絡(luò)，其公式如下：

式中，Ci是節(jié)點i所屬的社團，當否則為0；Q值在0和1之間，Q值越大說明該算法對于劃分社團結(jié)構(gòu)越有效。一般以Q=0.3作為網(wǎng)絡(luò)具有明顯社團結(jié)構(gòu)的下界。

3　數(shù)值仿真與結(jié)果分析

為了測試MEL算法的性能，分別利用人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)進行社團劃分實驗。在實驗中，與常見典型社團劃分算法進行了比較，參與對比的算法如下。

1)模塊度矩陣譜聚類[15]：以模塊度矩陣最大特征值對應(yīng)的特征向量來逐次將網(wǎng)絡(luò)節(jié)點進行二分，記為SOM(spectral optimization method)；

2)基于模塊度的模擬退火算法[28]：首先隨機生成一個初始解；在每次迭代中，在當前解的基礎(chǔ)上產(chǎn)生一個新的候選解，由模塊度函數(shù)判斷其優(yōu)劣，并采用模擬退火策略中的Metropolis準則決定是否接受該候選解，記為SA(simulated annealing)。

3.1人工基準網(wǎng)絡(luò)

人工網(wǎng)絡(luò)按照已知的社團結(jié)構(gòu)產(chǎn)生，可以測試不同算法劃分社團結(jié)構(gòu)的有效性。

采用兩種廣泛使用的人工生成網(wǎng)絡(luò)來測試算法的性能，分別為GN(Girvan-Newman)[5]和LF (Lancichinetti-Fortunato)[27]基準網(wǎng)絡(luò)。

1)GN基準網(wǎng)絡(luò)

本文測試了兩種類型的GN網(wǎng)絡(luò)，包含128個節(jié)點。第一種為社團結(jié)構(gòu)數(shù)量為4，每個社團含有32個節(jié)點，即社團規(guī)模是均勻分布的，記為GN1；另外一種為社團結(jié)構(gòu)規(guī)模不均勻的情況，記為GN2。本文產(chǎn)生的GN網(wǎng)絡(luò)為有向網(wǎng)絡(luò)，每個節(jié)點的平均入度為10。另外還引入了一個能刻畫網(wǎng)絡(luò)社團結(jié)構(gòu)的參數(shù)μ，它是一個混合比例，是網(wǎng)絡(luò)中的節(jié)點連接社團外部的度與該節(jié)點總的度數(shù)的比例。隨著μ的增加，網(wǎng)絡(luò)的社團結(jié)構(gòu)越不明顯。

2)LF基準網(wǎng)絡(luò)

為了進一步評估本文算法的精度，采用了另一種人工基準網(wǎng)絡(luò)。該網(wǎng)絡(luò)與GN網(wǎng)絡(luò)的不同在于網(wǎng)絡(luò)中的節(jié)點的度分布和社團規(guī)模分布均服從冪律分布，這一點與真實世界網(wǎng)絡(luò)更為相似。本文選取的LF網(wǎng)絡(luò)的參數(shù)如下：網(wǎng)絡(luò)的節(jié)點數(shù)為1 000，節(jié)點的平均入度為20，最大入度值為50。

本文測試了兩種不同社團大小規(guī)模分布的網(wǎng)絡(luò)。一個是社團結(jié)構(gòu)大小在10～50之間，記為LF1；一個是20～100之間，記為LF2。

對于這兩種網(wǎng)絡(luò)的測試結(jié)果如圖2所示。從中可以看出，本文的算法在探索有向網(wǎng)絡(luò)的社團結(jié)構(gòu)時的性能。圖2a為GN網(wǎng)絡(luò)中社團結(jié)構(gòu)規(guī)模均勻的情況，當μ≤0.4時即網(wǎng)絡(luò)社團結(jié)構(gòu)比較明顯，本文的算法跟SA算法所得到的NMI的值都能達到1，能準確地劃分網(wǎng)絡(luò)的社團結(jié)構(gòu)。隨著μ的增加，當0.4＜μ≤0.5時，本文算法所取得NMI值有所下降，但比SA算法取得的效果要好。圖2b顯示了GN網(wǎng)絡(luò)社團結(jié)構(gòu)規(guī)模分布不均勻的實驗結(jié)果，結(jié)果跟圖2a類似，可以發(fā)現(xiàn)當網(wǎng)絡(luò)中社團結(jié)構(gòu)明顯時即μ≤0.4，本文的算法能準確劃分社團結(jié)構(gòu)。并且當μ＞0.4時，即網(wǎng)絡(luò)社團結(jié)構(gòu)越來越不明顯時，MEL算法劃分社團結(jié)構(gòu)的效果要優(yōu)于SA和SOM算法。當μ=0.5時，MEL算法所得NMI值比SA算法提高了9.50%。

圖2　人工基準網(wǎng)絡(luò)上MEL，SOM和SA算法的實驗結(jié)果

圖2c～圖2d給出了每種算法的NMI值在LF網(wǎng)絡(luò)上隨混合參數(shù)μ的變化趨勢。可以看出，當μ≤0.7時，本文算法所得到的NMI的值接近于1，并且略優(yōu)于SA算法，能較為準確地劃分網(wǎng)絡(luò)的社團結(jié)構(gòu)。當0.7＜μ≤0.8時，即網(wǎng)絡(luò)的社團結(jié)構(gòu)并不明顯，SA算法明顯下降，本文的算法也有所下降但NMI值仍大于其他兩種算法。實驗結(jié)果表明本文算法在有向網(wǎng)絡(luò)探索社團結(jié)構(gòu)上的有效性。

3.2實證數(shù)據(jù)

本文使用的數(shù)據(jù)為美國伊利諾斯州的一個中學朋友關(guān)系的社會網(wǎng)絡(luò)[34]。該網(wǎng)絡(luò)為有向的朋友關(guān)系，節(jié)點代表一個人，邊代表他們之間的選擇朋友關(guān)系。該網(wǎng)絡(luò)有70個節(jié)點和366條邊。用MEL、SOM和SA這3種算法對該網(wǎng)絡(luò)進行社團結(jié)構(gòu)劃分，然后計算得到了每種算法的模塊度值如表1所示。

表1 不同算法社團劃分的Q值比較

從表1可以得知MEL算法比其他兩種算法Q值分別提高了17.28%和19.21%，說明本文算法對實際社交網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分也有一定的有效性。

然而，由于真實網(wǎng)絡(luò)的社團結(jié)構(gòu)的數(shù)量是未知的，因此，本文首先要解決的一個問題是將真實網(wǎng)絡(luò)的社團結(jié)構(gòu)個數(shù)找出來。本文根據(jù)鄰接矩陣的譜性質(zhì)[21]，即具有社團結(jié)構(gòu)的網(wǎng)絡(luò)，它的鄰接矩陣的c個特征值與其他特征值相差較遠，因此可以得到網(wǎng)絡(luò)的社團結(jié)構(gòu)的個數(shù)。通過該方法計算得到了本文實證網(wǎng)絡(luò)的社團結(jié)構(gòu)個數(shù)為10。

4　結(jié) 束 語

本文考慮多個拉普拉斯矩陣的特征向量，提出了一種譜聚類算法來探索社團結(jié)構(gòu)。首先計算有向網(wǎng)絡(luò)的拉普拉斯矩陣，并得到其特征向量。然后，取前c個作為聚類目標得到網(wǎng)絡(luò)的社團結(jié)構(gòu)。人工網(wǎng)絡(luò)的實驗結(jié)果表明該算法能有效劃分網(wǎng)絡(luò)的社團結(jié)構(gòu)。當社團結(jié)構(gòu)明顯時，本文算法能準確地劃分網(wǎng)絡(luò)的社團結(jié)構(gòu)；當網(wǎng)絡(luò)社團結(jié)構(gòu)不明顯時，與模塊度的譜優(yōu)化和模擬退火算法相比，本文算法取得的效果更好。在實證網(wǎng)絡(luò)上，模塊度Q分別提高了17.28%和19.21%。本文算法考慮了多個特征向量所包含的社團結(jié)構(gòu)信息，并沒有迭代過程，因此算法較為簡單和高效。

本文利用拉普拉斯矩陣的多個特征向量對有向網(wǎng)絡(luò)的社團結(jié)構(gòu)進行了劃分，該工作可以進一步擴展，比如對于非強連通網(wǎng)絡(luò)拉普拉斯矩陣的形式可以用其他方法[35-36]修正轉(zhuǎn)移概率矩陣的形式，算法最后一步也可以用其他聚類算法來代替k-means算法等。本文的工作有助于研究者認識有向網(wǎng)絡(luò)的拉普拉斯矩陣特征向量與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系。

[1]狄增如. 系統(tǒng)科學視角下的復雜網(wǎng)絡(luò)研究[J]. 上海理工大學學報,2011,33(2): 111-116. DI Zeng-ru. Research of complex networks from the view point of systems science[J]. Journal of University of Shanghai for Science and Technology,2011,33(2): 111-116.

[2]PALLA G,BARABáSI A L,VICSEK T. Quantifying social group evolution[J]. Nature,2007,446(7136): 664-667.

[3]ONNELA J P,SARAM?KI J,HYV?NEN J,et al. Structure and tie strengths in mobile communication networks[J]. Proceedings of the National Academy of Sciences,2007,104(18): 7332-7336.

[4]BARABáSI A L,OLTVAI Z N. Network biology: Understanding the cell's functional organization[J]. Nature Reviews Genetics,2004,5(2): 101-113.

[5]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.

[6]NEWMAN M E J,GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2): 026113.

[7]FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3): 75-174.

[8]PAN Y,LI D H,LIU J G,et al. Detecting community structure in complex networks via node similarity[J]. Physica A: Statistical Mechanics and Its Applications,2010,389(14): 2849-2857.

[9]宣照國,苗靜,黨延忠,等. 科研領(lǐng)域關(guān)聯(lián)網(wǎng)絡(luò)的社團結(jié)構(gòu)分析[J]. 上海理工大學學報,2008,30(3): 249-252. XUAN Zhao-guo,MIAO Jing,DANG Yan-zhong,et al. Community structure of Chinese nature science basic research weighted networks[J]. Journal of University of Shanghai for Science and Technology,2008,30(3): 249-252.

[10]邵鳳,郭強,曾詩奇,等. 微博系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)的研究進展[J]. 電子科技大學學報,2014,43(2): 174-183. SHAO Feng,GUO Qiang,ZENG Shi-qi,et al. Research progress of the microblog system structures[J]. Journal of University of Electronic Science and Technology of China,2014,43(2): 174-183.

[11]劉建國,任卓明,郭強,等. 復雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進展[J]. 物理學報,2013,62(17): 178901. LIU Jian-guo,REN Zhuo-ming,GUO Qiang,et al. Node importance ranking of complex networks[J]. Acta Phys Sin,2013,62(17): 178901.

[12]MALLIAROS F D,VAZIRGIANNIS M. Clustering and community detection in directed networks: a survey[J]. Physics Reports,2013,533(4): 95-142.

[13]NEWMAN M E J,LEICHT E A. Mixture models and exploratory analysis in networks[J]. Proceedings of the National Academy of Sciences,2007,104(23): 9564-9569.

[14]ROSVALL M,BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences,2008,105(4): 1118-1123.

[15]LEICHT E A,NEWMAN M E J. Community structure in directed networks[J]. Physical Review Letters,2008,100(11): 118703.

[16]NEWMAN M E J. Spectral methods for community detection and graph partitioning[J]. Physical Review E,2013,88(4): 042822.

[17]GONG X,LI K,Li M,et al. A spectral algorithm of community identification[J]. EPL (Europhysics Letters),2013,101(4): 48001.

[18]KRZAKALA F,MOORE C,MOSSEL E,et al. Spectral redemption in clustering sparse networks[J]. Proceedings of the National Academy of Sciences,2013,110(52): 20935-20940.

[19]WANG X,QIAN B,DAVIDSON I. On constrained spectral clustering and its applications[J]. Data Mining and Knowledge Discovery,2014,28(1): 1-30.

[20]CHAUHAN S,GIRVAN M,OTT E. Spectral properties of networks with community structure[J]. Physical Review E,2009,80(5): 056114.

[21]ARENAS A,DíAZ-GUILERA A,PéREZ-VICENTE C J. Synchronization reveals topological scales in complex networks[J]. Physical Review Letters,2006,96(11): 114102.

[22]CHENG X Q,SHEN H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics: Theory and Experiment,2010,2010(04): P04024.

[23]SHEN H W,CHENG X Q. Spectral methods for the detection of network community structure: a comparative analysis[J]. Journal of Statistical Mechanics: Theory and Experiment,2010(10): P10020.

[24]VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing,2007,17(4): 395-416.

[25]CHUNG F. Laplacians and the Cheeger inequality for directed graphs[J]. Annals of Combinatorics,2005,9(1): 1-19.

[26]GLEICH D. Hierarchical directed spectral graph partitioning[R]. California: Stanford University,2006.

[27]LANCICHINETTI A,FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E,2009,80(1): 016118.

[28]GUIMERA R,AMARAL L A N. Cartography of complex networks: Modules and universal roles[J]. Journal of Statistical Mechanics: Theory and Experiment,2005(2): P02001.

[29]PONS P,LATAPY M. Computing communities in large networks using random walks[J]. J Graph Algorithms Appl,2006,10(2): 191-218.

[30]LOVáSZ L. Random walks on graphs: a survey[J]. Combinatorics,Paul Erdos is Eighty,1993,2(1): 1-46.

[31]LANCICHINETTI A,FORTUNATO S. Community detection algorithms: a comparative analysis[J]. Physical Review E,2009,80(5): 056117.

[32]DANON L,DIAZ-GUILERA A,DUCH J,et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment,2005(9): P09008.

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

[34]COLEMAN J S. Introduction to mathematical sociology [M]. London: Free Press Glencoe,1964.

[35]BAUER F. Normalized graph Laplacians for directed graphs[J]. Linear Algebra and its Applications,2012,436(11): 4193-4222.

[36]TANG L,LI S,LIN J. Community structure detection based on the neighbor node degree information[J]. Int J Mod Phys C,2015,27(4): 1650046.

編輯蔣曉

Detecting Community Structure in Directed Networks Via Multiple Eigenvectors

YANG Kai1,GUO Qiang1,LIU Xiao-lu1,and LIU Jian-guo1,2
(1. Research Center of Complex Systems Science,University of Shanghai for Science and TechnologyYangpu Shanghai200093; 2. Laboratory Center,Shanghai University of Finance and EconomicsYangpu Shanghai200433)

Detecting community structure of directed networks is of significance for understanding the structures and functions of complex systems. In this paper,we develop a spectral algorithm using multiple eigenvectors of the Laplacian matrix (MEL)in directed networks,where the c eigenvectors of the smallest eigenvalues of the Laplacian matrix are taken into account. We compare with the spectral optimization method (SOM)and simulated annealing (SA)algorithm of modularity matrix in directed networks on synthetic and empirical networks. The experimental results indicate that,the values of the normalized mutual information (NMI)obtained by our algorithm are approximated 1 when the community structures are clearly. The proposed algorithm outperforms the SOM and SA algorithms when the community structures are not clearly. In addition,the numerical results for empirical data set show that the modularity values Q could be enhanced by 17.28% and 19.21% respectively. This work may be helpful to analyze the relationship between the properties of Laplacian matrix and community structures in directed networks.

community structure;directed networks;Laplacian matrix;spectral clustering

N949

A

10.3969/j.issn.1001-0548.2016.06.024

2015 ? 08 ? 09；

2015 ? 12 ? 25

國家自然科學基金(71371125,61374177,71271036,71271126)；上海市自然科學基金(14ZR1427800)；上海市東方學者特聘教授項目；上海市曙光學者項目(14SG42)

楊凱(1987 ? )，男，博士生，主要從事社會網(wǎng)絡(luò)結(jié)構(gòu)分析方面的研究.