楊　凱，郭　強(qiáng)，劉曉露，劉建國,2

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

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

楊凱1，郭強(qiáng)1，劉曉露1，劉建國1,2

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

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

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

1　研究背景介紹

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

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

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

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

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

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

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

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

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

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

2.2MEL算法描述

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

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

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

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

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

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

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

2.3評價指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 不同算法社團(tuán)劃分的Q值比較

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

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

4　結(jié) 束 語

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

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

[1]狄增如. 系統(tǒng)科學(xué)視角下的復(fù)雜網(wǎng)絡(luò)研究[J]. 上海理工大學(xué)學(xué)報,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ò)的社團(tuán)結(jié)構(gòu)分析[J]. 上海理工大學(xué)學(xué)報,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]邵鳳,郭強(qiáng),曾詩奇,等. 微博系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)的研究進(jìn)展[J]. 電子科技大學(xué)學(xué)報,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]劉建國,任卓明,郭強(qiáng),等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究進(jìn)展[J]. 物理學(xué)報,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

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

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