基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法*

周 旸，陳曉云+，程建軍,2，劉 偉，苗海飛

1.蘭州大學(xué) 信息科學(xué)與工程學(xué)院，蘭州 730000

2.甘肅省資源環(huán)境科學(xué)數(shù)據(jù)工程技術(shù)研究中心，蘭州 730000

基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法*

周 旸1，陳曉云1+，程建軍1,2，劉 偉1，苗海飛1

1.蘭州大學(xué) 信息科學(xué)與工程學(xué)院，蘭州 730000

2.甘肅省資源環(huán)境科學(xué)數(shù)據(jù)工程技術(shù)研究中心，蘭州 730000

針對傳統(tǒng)譜二分社團(tuán)檢測算法一般只使用某一特定的特征向量對網(wǎng)絡(luò)進(jìn)行劃分，并不能保證能夠得到最佳的社團(tuán)結(jié)構(gòu)這一缺陷，提出了一種使用最優(yōu)特征向量的譜二分社團(tuán)檢測方法。該方法利用網(wǎng)絡(luò)/子網(wǎng)絡(luò)轉(zhuǎn)移矩陣的特征向量持續(xù)將網(wǎng)絡(luò)分裂為若干個(gè)子網(wǎng)絡(luò)，分裂過程并不固定使用單一的、特定的特征向量，每次分裂使用的是能使得模塊度增量最大的一個(gè)特征向量。此外，為了充分利用網(wǎng)絡(luò)的拓?fù)湫畔?，還利用網(wǎng)絡(luò)中每條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)擁有的共同鄰居的信息，將原始網(wǎng)絡(luò)轉(zhuǎn)換為帶權(quán)的網(wǎng)絡(luò)，并基于此帶權(quán)網(wǎng)絡(luò)的轉(zhuǎn)移矩陣，使用最優(yōu)特征向量持續(xù)將其劃分為若干個(gè)子網(wǎng)絡(luò)，得到其社團(tuán)結(jié)構(gòu)。為了驗(yàn)證這兩種方法的有效性，在7個(gè)實(shí)際網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證實(shí)，該方法能夠有效地從網(wǎng)絡(luò)中提取高質(zhì)量的社團(tuán)結(jié)構(gòu)。

社團(tuán)檢測；譜二分法；特征值；特征向量；模塊度

1 引言

社團(tuán)結(jié)構(gòu)是很多復(fù)雜網(wǎng)絡(luò)擁有的顯著的結(jié)構(gòu)特征，表現(xiàn)為網(wǎng)絡(luò)中的頂點(diǎn)能夠被劃分成不同的組，同一組內(nèi)的頂點(diǎn)之間聯(lián)系十分緊密，不同組的頂點(diǎn)之間的聯(lián)系較為稀疏，其中每一個(gè)組即為一個(gè)社團(tuán)。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)往往對應(yīng)于由具有相似特性的頂點(diǎn)組成的功能模塊，如社會關(guān)系網(wǎng)絡(luò)[1-2]中的社團(tuán)往往對應(yīng)于擁有相同興趣或是相同職業(yè)的一組人，蛋白質(zhì)相互作用網(wǎng)絡(luò)[3-4]中的社團(tuán)可能是一組具有特定功能或特性的蛋白質(zhì)分子。因此提取復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，對于研究網(wǎng)絡(luò)的結(jié)構(gòu)，確定網(wǎng)絡(luò)的功能，理解結(jié)構(gòu)與功能之間的對應(yīng)關(guān)系而言，提供了一種有效的研究手段和方法。

自從Newman等人提出GN（Grivan-Newman）算法[5]以來，社團(tuán)檢測方面的研究引起了研究人員的普遍關(guān)注，已經(jīng)提出了大量的社團(tuán)檢測算法，其中包括譜分析方法[6-12]、模塊度優(yōu)化方法[13-16]等。譜分析方法由于擁有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)公式推導(dǎo)過程作為其理論基礎(chǔ)而得到廣泛的應(yīng)用；而模塊度優(yōu)化方法以模塊度指導(dǎo)社團(tuán)劃分的方向，如Newman等人提出的FastQ算法[14]，通過不斷合并使得模塊度增量最大的兩個(gè)子圖，獲得模塊度最大的社團(tuán)結(jié)構(gòu)；Barder等人[13]將模塊度優(yōu)化的方法應(yīng)用到LPA（label-propagation algorithm）當(dāng)中，讓每個(gè)頂點(diǎn)選取能夠獲得最大模塊度的標(biāo)簽，控制標(biāo)簽傳播的方向。

一般情況下，譜分析方法使用諸如鄰接矩陣、拉普拉斯矩陣等與網(wǎng)絡(luò)關(guān)聯(lián)的矩陣的特征值、特征向量對網(wǎng)絡(luò)進(jìn)行劃分，得到社團(tuán)結(jié)構(gòu)。例如，Cheng等人[12]利用與隨機(jī)游走對應(yīng)的拉普拉斯矩陣揭示網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)。Lange等人[9]利用歸一化的拉普拉斯矩陣的特征譜提取生物神經(jīng)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。譜二分法是譜分析方法的一種特殊情況，這一類方法利用相關(guān)矩陣的一個(gè)或少數(shù)幾個(gè)特征向量對網(wǎng)絡(luò)進(jìn)行劃分，每次將原網(wǎng)絡(luò)劃分為兩個(gè)子網(wǎng)絡(luò)。例如，Pothen等人[10]利用拉普拉斯矩陣的最小非零特征值對應(yīng)的特征向量，以其元素的中位數(shù)為劃分界線，將對應(yīng)的頂點(diǎn)分別劃分到兩個(gè)社團(tuán)之中。Newman[6,11]基于歸一化拉普拉斯矩陣，給出了解決隨機(jī)塊模型、圖的最小割剖分和社團(tuán)檢測三種問題的譜二分法。在Pothen的譜二分法的基礎(chǔ)上，Donetti等人[7]利用一個(gè)維度可調(diào)的特征向量空間，尋找能夠使得模塊度達(dá)到最大的社團(tuán)結(jié)構(gòu)。而Newman等人[8,17]利用基于模塊度矩陣的譜二分法將網(wǎng)絡(luò)遞歸地進(jìn)行分裂，得到社團(tuán)結(jié)構(gòu)。

然而，傳統(tǒng)的譜二分方法通常是按照某一特定的特征向量中元素的分布情況，通過對網(wǎng)絡(luò)進(jìn)行持續(xù)分裂，從而提取網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，但這種方法無法保證每一次分裂一定是最優(yōu)的。此外，文獻(xiàn)[11]中的例子表明，不同的網(wǎng)絡(luò)可能需要使用不同的特征向量進(jìn)行分裂，才能得到最佳的社團(tuán)結(jié)構(gòu)。因此，本文結(jié)合模塊度優(yōu)化的思想，提出了一種基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法。本文方法利用網(wǎng)絡(luò)轉(zhuǎn)移矩陣的特征向量對網(wǎng)絡(luò)/子網(wǎng)絡(luò)進(jìn)行持續(xù)分裂，但分裂過程并不是固定使用單一的特征向量。相反，每一次分裂使用的是能使得模塊度增量最大的一個(gè)特征向量。在此基礎(chǔ)上，為了充分利用網(wǎng)絡(luò)的拓?fù)湫畔?，利用相鄰頂點(diǎn)之間的公共鄰居信息為這兩個(gè)頂點(diǎn)之間的邊計(jì)算權(quán)值，將原網(wǎng)絡(luò)轉(zhuǎn)換為帶權(quán)網(wǎng)絡(luò)，并利用轉(zhuǎn)換后帶權(quán)網(wǎng)絡(luò)轉(zhuǎn)移矩陣的特征向量，使用同樣的譜二分法對網(wǎng)絡(luò)進(jìn)行分裂，從而提取社團(tuán)結(jié)構(gòu)。

為了驗(yàn)證本文提出的社團(tuán)檢測方法，在7個(gè)實(shí)際網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)，并與一些已有的社團(tuán)檢測算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果證實(shí)，本文方法能夠有效地從網(wǎng)絡(luò)中提取高質(zhì)量的社團(tuán)結(jié)構(gòu)。

2 方法描述

本文使用的原始網(wǎng)絡(luò)都是無權(quán)無向圖，記為G(V,E)，其中V和E分別是網(wǎng)絡(luò)的頂點(diǎn)和邊的集合，記n=|V|，m=|E|。

2.1 基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法

本文提出的譜二分社團(tuán)檢測方法以模塊度最大化為目標(biāo)。模塊度的計(jì)算公式為：

其中，di、dj分別為頂點(diǎn)i、j相連的邊的數(shù)目；當(dāng)頂點(diǎn)i和j之間有邊相連時(shí)，Aij=1，否則，Aij=0；δ(x,y)=1當(dāng)且僅當(dāng)x=y，否則δ(x,y)=0；ci、cj分別是頂點(diǎn)i和頂點(diǎn)j所屬社團(tuán)的編號。二分法每次將網(wǎng)絡(luò)分裂為兩個(gè)子網(wǎng)絡(luò)，可定義一個(gè)向量x記錄每個(gè)頂點(diǎn)屬于哪個(gè)子網(wǎng)絡(luò)，其元素為：

因此，本文方法的目標(biāo)就是在每次分裂的時(shí)候確定每個(gè)頂點(diǎn)的歸屬，使得模塊度Q值最大化。以此為出發(fā)點(diǎn)，Newman在文獻(xiàn)[11]中推導(dǎo)得出：

其中λ為廣義特征方程（3）的特征值：

其中A為網(wǎng)絡(luò)的鄰接矩陣，其元素為Aij；D為對角矩陣，其元素；s為λ對應(yīng)的特征向量。當(dāng)網(wǎng)絡(luò)連通時(shí)，矩陣D可逆，式（3）變形為：

其中D-1A即為網(wǎng)絡(luò)的轉(zhuǎn)移矩陣，記作T，即：

亦即，λ為特征方程（5）的最大的特征值時(shí)，模塊度Q取得最大值。然而，文獻(xiàn)[11]的推導(dǎo)過程指出，λ不能取特征方程（5）的最大特征值，因?yàn)閟=(1,1,…,1)必然是特征方程（5）的一個(gè)特征向量，根據(jù)Perron-Frobenius定理，該特征向量對應(yīng)的特征值必然為該特征方程最大的特征值，然而該特征向量無法滿足推導(dǎo)過程的一個(gè)約束條件。因此，只能退而求其次，選取特征方程（5）次大的特征值作為λ的值，其對應(yīng)的特征向量s即為解向量x。然而，s中元素值為任意實(shí)數(shù)，x中元素值為±1。可以簡單地將s中的元素向距其最近的+1或者-1靠近，等價(jià)于按照s中元素的符號將網(wǎng)絡(luò)分裂為兩個(gè)子網(wǎng)絡(luò)。

然而，從模塊度最大化的角度出發(fā)考慮，上述分裂過程并不能保證分裂后子網(wǎng)絡(luò)對應(yīng)的模塊度一定是最大的，即不能保證得到的社團(tuán)結(jié)構(gòu)是最優(yōu)的。文獻(xiàn)[11]在人工合成網(wǎng)絡(luò)、海豚社交網(wǎng)絡(luò)、美國政治書籍網(wǎng)絡(luò)和美國政治博客網(wǎng)絡(luò)上的研究結(jié)果表明，不同的網(wǎng)絡(luò)可能需要使用不同的特征向量進(jìn)行分裂，才能得到最佳的社團(tuán)結(jié)構(gòu)。因此，本文在分裂過程中并未固定使用某一個(gè)特征向量對網(wǎng)絡(luò)進(jìn)行分裂，而是依次嘗試轉(zhuǎn)移矩陣除最大特征值之外的每一個(gè)特征值對應(yīng)的特征向量，按其元素的符號將網(wǎng)絡(luò)分別進(jìn)行分裂，并計(jì)算分裂后模塊度增量，選擇模塊度增量最大的一個(gè)分裂作為當(dāng)前網(wǎng)絡(luò)/子網(wǎng)絡(luò)分裂的結(jié)果。亦即，從模塊度最大化的角度而言，每次利用最優(yōu)的特征向量將網(wǎng)絡(luò)二分為兩個(gè)子網(wǎng)絡(luò)。

對于給定的網(wǎng)絡(luò)，首先按照上述方法對其進(jìn)行第一次分裂，得到兩個(gè)子網(wǎng)絡(luò)，每個(gè)子網(wǎng)絡(luò)對應(yīng)于一個(gè)社團(tuán)；隨后，對得到的兩個(gè)子網(wǎng)絡(luò)分別進(jìn)行進(jìn)一步的分裂；重復(fù)這一過程，直到對網(wǎng)絡(luò)/子網(wǎng)絡(luò)的分裂達(dá)到適當(dāng)?shù)某潭?，停止分裂過程。由于該方法的目標(biāo)是使模塊度最大化，若某個(gè)子網(wǎng)絡(luò)的分裂不能得到更大的模塊度，則停止對該子網(wǎng)絡(luò)的分裂。本文將該方法稱為BSOE（bisection spectral method based on the optimal eigenvectors），其具體步驟如算法1中偽代碼所示。

算法1基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法

其中，C是社團(tuán)的集合，初始情況下，網(wǎng)絡(luò)中所有頂點(diǎn)構(gòu)成一個(gè)社團(tuán)；接著對C中的每一個(gè)社團(tuán)Ci調(diào)用函數(shù)spectra_split()分裂得到兩個(gè)社團(tuán)，如果該分裂能夠使得模塊度值增大，則接受該次分裂，將社團(tuán)并入C中，并從C中移除Ci，否則丟棄該次分裂。函數(shù)spectra_split()實(shí)現(xiàn)基于最優(yōu)特征向量的譜二分算法：對于社團(tuán)Ci，首先構(gòu)造其對應(yīng)的子網(wǎng)絡(luò)，獲取其鄰接矩陣、對角矩陣，計(jì)算得到轉(zhuǎn)移矩陣，接著對轉(zhuǎn)移矩陣進(jìn)行特征值分解得到全部特征值和對應(yīng)的特征向量，然后利用除最大特征值對應(yīng)的特征向量以外的每一特征向量分別將該子網(wǎng)絡(luò)二分為兩個(gè)子網(wǎng)絡(luò)，從中選出能使得模塊度增量最大的兩個(gè)子網(wǎng)絡(luò)作為Ci分裂的結(jié)果，并將其和最大的模塊度增量一起返回。

其中函數(shù)delta_Q()負(fù)責(zé)計(jì)算每一分裂帶來的模塊度增量，F(xiàn)astQ算法中提出了將兩個(gè)社團(tuán)合并為Ci時(shí)模塊度增量的快速計(jì)算公式：，其中ei1,i2是社團(tuán)之間的邊在網(wǎng)絡(luò)所有邊中所占的比例，而則是分別與社團(tuán)中頂點(diǎn)相連的邊在網(wǎng)絡(luò)所有邊中所占的比例。函數(shù)delta_Q()需要計(jì)算將Ci分裂為帶來的模塊度增量，與合并時(shí)的情況正好相反，分裂帶來的模塊度增量為：

同樣可以快速地進(jìn)行計(jì)算。

2.2 帶權(quán)的最優(yōu)特征向量譜二分社團(tuán)檢測方法

算法1給出的基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法基于無權(quán)無向圖的轉(zhuǎn)移矩陣，而轉(zhuǎn)移矩陣從網(wǎng)絡(luò)的鄰接矩陣演化得到。網(wǎng)絡(luò)的鄰接矩陣體現(xiàn)了與每個(gè)頂點(diǎn)相連的邊的信息，然而只依據(jù)頂點(diǎn)自身的這些拓?fù)湫畔o法簡單地判定該頂點(diǎn)的社團(tuán)歸屬。相反，頂點(diǎn)之間的公共鄰居信息有助于確定兩個(gè)頂點(diǎn)之間的社團(tuán)歸屬關(guān)系，通常而言，兩個(gè)頂點(diǎn)的公共鄰居越多，這兩個(gè)頂點(diǎn)越有可能同屬于一個(gè)社團(tuán)。圖1給出了一個(gè)簡單的示例網(wǎng)絡(luò)，其中邊(a,d)連接了兩個(gè)社團(tuán)，是社團(tuán)之間的邊?？梢钥闯?，該邊連接的兩個(gè)頂點(diǎn)的公共鄰居要明顯少于社團(tuán)內(nèi)部邊連接的頂點(diǎn)。因此，頂點(diǎn)之間的公共鄰居信息可用以衡量連接兩個(gè)頂點(diǎn)的邊在社團(tuán)劃分中的作用。

Fig.1 Example of community structure,the edge(a,d)connects two communities圖1 社團(tuán)示例，邊(a,d)連接兩個(gè)社團(tuán)

如果能將頂點(diǎn)的公共鄰居信息直接集成到網(wǎng)絡(luò)的鄰接矩陣中，再應(yīng)用前面提出的譜二分方法檢測社團(tuán)結(jié)構(gòu)，能夠提高社團(tuán)結(jié)構(gòu)的質(zhì)量?？紤]鄰接矩陣的實(shí)際含義，將頂點(diǎn)的公共鄰居信息集成到網(wǎng)絡(luò)的鄰接矩陣中，相當(dāng)于將原始網(wǎng)絡(luò)轉(zhuǎn)換為帶權(quán)網(wǎng)絡(luò)。本文采用與頂點(diǎn)u和v的公共鄰居信息計(jì)算邊(u,v)的權(quán)值w(u,v)，計(jì)算公式為：

其中，N(u)和N(v)分別是頂點(diǎn)u和v的鄰居頂點(diǎn)集合。

經(jīng)過轉(zhuǎn)換得到帶權(quán)網(wǎng)絡(luò)后，再利用算法1從帶權(quán)網(wǎng)絡(luò)中提取社團(tuán)結(jié)構(gòu)。不過由于網(wǎng)絡(luò)的邊帶有權(quán)值，應(yīng)對算法1進(jìn)行適應(yīng)性改造：鄰接矩陣A的元素值不再只是0或1，而是對應(yīng)邊的權(quán)值，即Aij=w(i,j)，對角矩陣D的元素。此外，模塊度的計(jì)算也需要變更為帶權(quán)網(wǎng)絡(luò)的模塊度，式（1）中m的含義應(yīng)變?yōu)榫W(wǎng)絡(luò)中所有邊的權(quán)值之和，di和dj應(yīng)為分別與頂點(diǎn)i和頂點(diǎn)j關(guān)聯(lián)的邊的權(quán)值之和；式（6）中應(yīng)變?yōu)樯鐖F(tuán)之間的邊的權(quán)值之和在網(wǎng)絡(luò)所有邊的總權(quán)值中所占的比例，而應(yīng)為分別與社團(tuán)中頂點(diǎn)相連的邊的權(quán)值之和在所有邊的總權(quán)值中所占的比例。

如此一來，社團(tuán)檢測過程中計(jì)算的模塊度是轉(zhuǎn)換后帶權(quán)網(wǎng)絡(luò)的模塊度，并不是基于原始網(wǎng)絡(luò)的真實(shí)模塊度，因此，在社團(tuán)檢測過程中，可能會出現(xiàn)過度分裂的情況，即有一些子網(wǎng)絡(luò)會被分裂為特別小的子網(wǎng)絡(luò)，這些特別小的子網(wǎng)絡(luò)無法被當(dāng)作可接受的社團(tuán)。因此，本文在譜二分方法分裂得到的子網(wǎng)絡(luò)基礎(chǔ)上，檢查每個(gè)子網(wǎng)絡(luò)的規(guī)模，將一些小的子網(wǎng)絡(luò)合并為較大的子網(wǎng)絡(luò)，得到最終的社團(tuán)結(jié)構(gòu)。與BSOE方法相區(qū)別，本文將該方法稱為WBSOE（weighted bisection spectral method based on the optimal eigenvectors），算法2中偽代碼給出了其大體框架。

算法2帶權(quán)的最優(yōu)特征向量譜二分社團(tuán)檢測方法

該方法大體上包含3個(gè)步驟：第一步調(diào)用Weight()函數(shù)將原始網(wǎng)絡(luò)轉(zhuǎn)換為帶權(quán)網(wǎng)絡(luò)；第二步調(diào)用改造后的BSOE方法將帶權(quán)網(wǎng)絡(luò)分裂為一系列子網(wǎng)絡(luò)；第三步調(diào)用Merge()函數(shù)將其中一些小的子網(wǎng)絡(luò)進(jìn)行合并，得到最終的社團(tuán)結(jié)構(gòu)。該框架中Weight()函數(shù)和Merge()函數(shù)的邏輯分別如算法3、算法4中偽代碼所示。

算法3無權(quán)網(wǎng)絡(luò)向帶權(quán)網(wǎng)絡(luò)轉(zhuǎn)換：Weight()函數(shù)

算法4合并較小的子網(wǎng)絡(luò)：Merge(C,G′)函數(shù)

算法3非常簡單，只需要按照式（7）計(jì)算網(wǎng)絡(luò)中每條邊的權(quán)值即可。算法4中，將原始網(wǎng)絡(luò)的平均度(davg)和輸入的參數(shù)t中的較小值設(shè)為閾值，當(dāng)社團(tuán)中包含的頂點(diǎn)數(shù)目小于該閾值時(shí)，表明該社團(tuán)規(guī)模過小，應(yīng)被并入其他社團(tuán)中。參數(shù)t與davg一起作用，控制社團(tuán)的最小規(guī)模。在大多數(shù)稀疏網(wǎng)絡(luò)上，平均度較小，起作用的是參數(shù)davg，在一些比較稠密的網(wǎng)絡(luò)上，davg的值較大，如果仍將規(guī)模小于davg的社團(tuán)合并到其他社團(tuán)，則有可能導(dǎo)致社團(tuán)檢測精度的損失。因此，需要使用參數(shù)t進(jìn)行調(diào)節(jié)。參數(shù)t的設(shè)置應(yīng)選擇一個(gè)與大多數(shù)稀疏網(wǎng)絡(luò)的平均度接近的值，建議選擇區(qū)間[5,9]內(nèi)的正數(shù)。參考“六度分割理論”，本文的實(shí)驗(yàn)中統(tǒng)一設(shè)置t的值為經(jīng)驗(yàn)值6。接著，算法4計(jì)算規(guī)模過小的社團(tuán)與其他社團(tuán)之間的相似性，并將該社團(tuán)并入與其相似性最大的那個(gè)社團(tuán)。該算法中，用位于社團(tuán)Ci和社團(tuán)Cj之間邊所帶的權(quán)值計(jì)算Ci和Cj之間的相似性，即：

3 實(shí)驗(yàn)

本文在7個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，對BSOE方法和WBSOE方法進(jìn)行驗(yàn)證，使用模塊度來衡量算法得到的社團(tuán)結(jié)構(gòu)的質(zhì)量，并將BSOE方法、WBSOE方法的結(jié)果與5個(gè)已有的社團(tuán)檢測算法進(jìn)行比較，下面給出實(shí)驗(yàn)過程及實(shí)驗(yàn)結(jié)果。

3.1 實(shí)驗(yàn)設(shè)置

本文使用的7個(gè)數(shù)據(jù)集分別是空手道俱樂部網(wǎng)絡(luò)[18]、Risk 游戲地圖網(wǎng)絡(luò)[19]、海豚社交網(wǎng)絡(luò)[20]、科學(xué)家合作網(wǎng)絡(luò)[21-22]、2000年賽季美國大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)[19]、metabolic網(wǎng)絡(luò)[4]和 email網(wǎng)絡(luò)[23]，各網(wǎng)絡(luò)數(shù)據(jù)集的統(tǒng)計(jì)信息如表1所示。這7個(gè)網(wǎng)絡(luò)均是被廣泛認(rèn)可的基準(zhǔn)測試數(shù)據(jù)集，其中前5個(gè)網(wǎng)絡(luò)的實(shí)際社團(tuán)結(jié)構(gòu)已知，能夠較好地體現(xiàn)社團(tuán)檢測算法的有效性和準(zhǔn)確性。

Table 1 Parameters of real-world datasets表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)

同時(shí)，本文將BSOE方法、WBSOE方法的結(jié)果與相關(guān)5個(gè)算法的結(jié)果進(jìn)行了比較，這5個(gè)算法分別是譜聚類[24]（spectral clustering）、Newman2006[8,17]、FastQ[14]、LPAm（label propagation algorithm under modularity constraint）[13]和 DD（dynamic distance）[25]算法。譜聚類算法和Newman2006算法都是譜分析方法，其中Newman2006算法是一種典型的譜二分算法；FastQ和LPAm這兩個(gè)算法均使用模塊度最優(yōu)策略指導(dǎo)社團(tuán)檢測過程；DD算法是一種基于頂點(diǎn)間動態(tài)距離的社團(tuán)檢測算法。

為了衡量各算法從網(wǎng)絡(luò)中提取的社團(tuán)結(jié)構(gòu)的質(zhì)量，采用模塊度標(biāo)準(zhǔn)作為首要度量標(biāo)準(zhǔn)，為每個(gè)結(jié)果計(jì)算模塊度值，模塊度的值越大，表明社團(tuán)內(nèi)部頂點(diǎn)間聯(lián)系越緊密，社團(tuán)結(jié)構(gòu)質(zhì)量越好。另外，由于前5個(gè)網(wǎng)絡(luò)數(shù)據(jù)集的標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)是已知的，使用NMI（normalized mutual information）[26]作為一個(gè)輔助的衡量標(biāo)準(zhǔn)，度量各算法在網(wǎng)絡(luò)上得到的社團(tuán)結(jié)構(gòu)與其標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)的相近程度。NMI取值范圍為[0,1]，其值越接近1，表明算法得到的社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)的標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)越接近。由于模塊度是一個(gè)內(nèi)部評價(jià)標(biāo)準(zhǔn)，它的計(jì)算與網(wǎng)絡(luò)的標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)之間不存在任何聯(lián)系，很多情況下，NMI的值與模塊度的值并不一致，它們從兩方面分別對算法提取得到的社團(tuán)結(jié)構(gòu)的質(zhì)量進(jìn)行衡量。

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

表2和表3分別記錄了本文算法和5個(gè)對比算法檢測得到的社團(tuán)結(jié)構(gòu)的模塊度和NMI值。由于metabolic網(wǎng)絡(luò)和email網(wǎng)絡(luò)的標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)未知，無法使用NMI對各算法的結(jié)果進(jìn)行度量，故表3沒有列出這兩個(gè)數(shù)據(jù)集的結(jié)果。其中，由于譜聚類方法和LPAm算法的結(jié)果具有不確定性，本文實(shí)驗(yàn)中將其分別在每個(gè)網(wǎng)絡(luò)上各運(yùn)行20次，選取出現(xiàn)最為頻繁的結(jié)果作為該算法的最終結(jié)果。

在所使用的7個(gè)實(shí)際網(wǎng)絡(luò)中，本文WBSOE方法和BOSE方法能夠在其中的5個(gè)網(wǎng)絡(luò)上得到模塊度值最好的社團(tuán)結(jié)構(gòu)，在科學(xué)家合作網(wǎng)絡(luò)和足球網(wǎng)絡(luò)上也取得了次好的結(jié)果；用NMI進(jìn)行衡量，WBSOE方法同樣能夠在2個(gè)網(wǎng)絡(luò)上取得最好結(jié)果，在其他網(wǎng)絡(luò)上也能取得比較靠前的成績。這證明WBSOE方法能夠有效地從網(wǎng)絡(luò)中提取出社團(tuán)結(jié)構(gòu)，并且社團(tuán)結(jié)構(gòu)的質(zhì)量也能夠得到保證。相反，除了FastQ算法外的其他4種算法在不同的網(wǎng)絡(luò)上得到的社團(tuán)結(jié)構(gòu)的質(zhì)量存在較大的波動。

Table 2 Modularity of different algorithms on world datasets表2 各算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果的模塊度值

Table 3 NMI of different algorithms on world datasets表3 各算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果的NMI值

對于足球網(wǎng)絡(luò)，BSOE算法和WBSOE算法在模塊度和NMI上并沒有取得最好的結(jié)果。這是因?yàn)樽闱蚓W(wǎng)絡(luò)中存在一個(gè)由4個(gè)頂點(diǎn)組成的社團(tuán)，BSOE算法和WBSOE算法都會將這個(gè)社團(tuán)合并到其他的社團(tuán)中去，故這兩個(gè)算法在足球網(wǎng)絡(luò)上難以取得超過DD算法的社團(tuán)結(jié)構(gòu)。即便如此，WBSOE算法也在足球網(wǎng)絡(luò)上取得了次優(yōu)的模塊度，NMI值也僅次于LPAm算法和DD算法。

對于作為WBSOE算法基礎(chǔ)的BSOE算法，在各網(wǎng)絡(luò)上取得的社團(tuán)結(jié)構(gòu)的質(zhì)量，無論是模塊度值還是NMI值大部分都遜色于WBSOE算法。即使如此，在所有7種算法中，BSOE算法仍然排在比較靠前的位置，表明該算法也具有較好的效果，也證明了WBSOE算法對BSOE算法的改進(jìn)是有效的，能夠顯著提高社團(tuán)檢測的質(zhì)量。

為了進(jìn)一步比較BSOE算法和WBSOE算法，著重分析這兩種算法在空手道俱樂部網(wǎng)絡(luò)和Risk游戲地圖網(wǎng)絡(luò)上的結(jié)果，并將其提取的社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)的標(biāo)準(zhǔn)社團(tuán)結(jié)構(gòu)進(jìn)行對比。圖2和圖3分別給出了BSOE方法和WBSOE方法在這兩個(gè)網(wǎng)絡(luò)上的檢測結(jié)果，圖中用同一種形狀和顏色畫出的頂點(diǎn)構(gòu)成一個(gè)社團(tuán)。

在圖2中，BSOE算法和WBSOE算法均將空手道俱樂部網(wǎng)絡(luò)劃分為4個(gè)不同的社團(tuán)，社團(tuán)數(shù)目均大于網(wǎng)絡(luò)的實(shí)際社團(tuán)數(shù)目。但是，從表2中的模塊度值可以得知，圖2（b）和圖2（c）中的社團(tuán)結(jié)構(gòu)擁有比圖2（a）中實(shí)際社團(tuán)結(jié)構(gòu)更高的模塊度值，表明這兩種方法在該網(wǎng)絡(luò)上檢測出的社團(tuán)結(jié)構(gòu)具有更高的質(zhì)量。對比圖2（b）與圖2（c）中社團(tuán)結(jié)構(gòu)可以看出，二者中僅有1個(gè)頂點(diǎn)的社團(tuán)歸屬不同，導(dǎo)致了兩者模塊度值和NMI值的差距。但這一結(jié)果表明WBSOE算法在細(xì)節(jié)處理上更優(yōu)于BSOE算法。

Fig.2 Zachary's karate club圖2 空手道俱樂部網(wǎng)絡(luò)

Fig.3 Risk map network圖3 Risk游戲地圖網(wǎng)絡(luò)

圖3展示的是BSOE方法和WBSOE方法在Risk游戲地圖網(wǎng)絡(luò)上的檢測結(jié)果。結(jié)合表2中的模塊度和NMI值可知，圖3（b）中社團(tuán)結(jié)構(gòu)與圖3（a）中社團(tuán)結(jié)構(gòu)存在較大差距，但二者具有相同的模塊度值。顯然，圖3（b）中對于頂點(diǎn)“10”和頂點(diǎn)“29”的劃分存在較為明顯的錯(cuò)誤，而這些錯(cuò)誤在圖3（c）中得到了修正，再次證明WBSOE算法對BSOE算法的改進(jìn)是有效的。圖3（c）中頂點(diǎn)“26”的社團(tuán)歸屬與實(shí)際社團(tuán)結(jié)構(gòu)中的差異，主要是由于該頂點(diǎn)關(guān)聯(lián)了6條邊，分別與3個(gè)社團(tuán)相連，每個(gè)社團(tuán)都有兩條邊與之相連。如果不考慮該頂點(diǎn)在Risk游戲中代表的物理含義，只考慮其拓?fù)浣Y(jié)構(gòu)的話，將其劃分到與之相連的任何一個(gè)社團(tuán)，均是合理的。將圖3（c）中社團(tuán)結(jié)構(gòu)與圖3（b）中社團(tuán)結(jié)構(gòu)的模塊度進(jìn)行對比，可以得知WBSOE方法獲得的社團(tuán)結(jié)構(gòu)具有更高的質(zhì)量。

綜上所述，上述實(shí)驗(yàn)證實(shí)了本文方法能夠有效地從網(wǎng)絡(luò)中提取出高質(zhì)量的社團(tuán)結(jié)構(gòu)，尤其是WBSOE算法，在所有5個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上均能取得最優(yōu)或次優(yōu)的成績，證明該算法具有較強(qiáng)的可靠性和穩(wěn)定性，能夠適應(yīng)大多數(shù)結(jié)構(gòu)的網(wǎng)絡(luò)。另外，WBSOE算法與BSOE算法的實(shí)驗(yàn)結(jié)果的對比，可以證實(shí)WBSOE算法對于BSOE算法的改進(jìn)是十分有效的，能夠明顯地提高社團(tuán)檢測的質(zhì)量以及社團(tuán)結(jié)構(gòu)的合理性。

4 結(jié)論

本文基于譜二分法，提出了一種能夠?qū)ふ易顑?yōu)的特征向量，并利用該向量對網(wǎng)絡(luò)進(jìn)行分裂的社團(tuán)檢測算法。同時(shí)，針對無權(quán)網(wǎng)絡(luò)上的譜二分法存在的問題，利用頂點(diǎn)之間的公共鄰居信息，將無權(quán)網(wǎng)絡(luò)轉(zhuǎn)換為帶權(quán)網(wǎng)絡(luò)，并將基于最優(yōu)特征向量的譜二分社團(tuán)檢測方法進(jìn)行了適應(yīng)性改造，使其能夠充分利用網(wǎng)絡(luò)的拓?fù)湫畔⑦M(jìn)行社團(tuán)檢測，提高社團(tuán)質(zhì)量。

本文還在7個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，以驗(yàn)證提出的兩個(gè)方法的有效性，并將檢測結(jié)果與另外5個(gè)相關(guān)算法的結(jié)果進(jìn)行了比較。實(shí)驗(yàn)結(jié)果證實(shí)，本文算法能夠有效地從網(wǎng)絡(luò)中提取出高質(zhì)量的社團(tuán)結(jié)構(gòu)。

[1]Mcauley J,Leskovec J.Discovering social circles in ego networks[J].ACM Transactions on Knowledge Discovery from Data,2014,8(1):4.

[2]Mcauley J,Leskovec J.Learning to discover social circles in ego networks[C]//Proceedings of the Advances in Neural Information Processing Systems 25,Lake Tahoe,USA,Dec 3-6,2012.Red Hook,USA:CurranAssociates,2012:539-547.

[3]Lewis A C,Jones N S,Porter M A,et al.The function of communities in protein interaction networks at multiple scales[J].BMC Systems Biology,2010,4(1):100.

[4]Jeong H,Tombor B,Albert R,et al.The large-scale organization of metabolic networks[J].Nature,2000,407(6804):651-654.

[5]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[6]Newman M E J.Community detection and graph partitioning[J].Europhysics Letters,2013,103(2):28003.

[7]Donetti L,Mu?oz M A.Detecting network communities:a new systematic and efficient algorithm[J].Journal of Statistical Mechanics:Theory and Experiment,2004,2004(10):10012.

[8]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.

[9]Lange S C D,Reus M A D,Heuvel M P V D.The Laplacian spectrum of neural networks[J].Frontiers in Computational Neuroscience,2014,7(7):189.

[10]Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis&Applications,1990,11(3):430-452.

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

[12]Cheng Xueqi,Shen Huawei.Uncovering the community structure associated with the diffusion dynamics on networks[J].Journal of Statistical Mechanics:Theory and Experiment,2010(4):147-167.

[13]Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):026129.

[14]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[15]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008(10):155-168.

[16]Sun Penggang,Gao L.A framework of mapping undirected to directed graphs for community detection[J].Information Sciences,2015,298:330-343.

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

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

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

[20]Lusseau D,Newman M E J.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society of London B:Biological Sciences,2004,271(S6):477-481.

[21]Newman M E J.Scientific collaboration networks I Network construction and fundamental results[J].Physical Review E,2001,64(1):016131.

[22]Newman M E J.Scientific collaboration networks II Shortest paths,weighted networks,and centrality[J].Physical Review E,2001,64(1):016132.

[23]Guimerà R,Danon L,Díaz-Guilera A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.

[24]Ng A Y,Jordan M I,Weiss Y.On spectral clustering:analysis and an algorithm[C]//Proceedings of the Advances in Neural Information Processing Systems 14,Vancouver,Canada,Dec 3-8,2001.Cambridge,USA:MIT Press,2002,2:849-856.

[25]Shao Junming,Han Zhichao,Yang Qinli,et al.Community detection based on distance dynamics[C]//Proceedings of the 21st International Conference on Knowledge Discovery and Data Mining,Sydney,Australia,Aug 10-13,2015.New York:ACM,2015:1075-1084.

[26]Fred A L N,Jain A K.Robust data clustering[C]//Proceedings of the 2003 International Conference on Computer Vision and Pattern Recognition,Madison,USA,Jun 18-20,2003.Piscataway,USA:IEEE,2003,2:128-133.

Bisection Spectral Community-Detection Methods Using Optimal Eigenvectors*

ZHOU Yang1,CHEN Xiaoyun1+,CHENG Jianjun1,2,LIU Wei1,MIAO Haifei1

1.School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,China
2.Gansu Resources and Environmental Science Data Engineering Technology Research Center,Lanzhou 730000,China

2016-09,Accepted 2016-11.

In general,the bisection spectral method always uses only one certain eigenvalue and its corresponding eigenvector to extract communities,which does not guarantee to obtain the best community structures.To solve this problem,this paper proposes a bisection spectral method based on the optimal eigenvectors,which utilizes the eigenvectors of transition matrices to partition the network/subnetwork into communities repeatedly,and the eigenvector used in each partition is the one whose bisection can lead to the largest modularity increment.Besides this,in order to encode the topological information into the proposed method,this paper also converts the original networks into weighted ones by utilizing the information of common neighbors of the two end vertices associated with each edge.Based on the transition matrix of the converted network,this paper applies the same bisection spectral method to extract communities.The experiments on 7 real-world networks are performed,and the experimental results show that the proposed method can extract the high-quality community structures from networks effectively.

community detection;bisection spectral method;eigenvalues;eigenvector;modularity

+Corresponding author:E-mail:chenxy@lzu.edu.cn

10.3778/j.issn.1673-9418.1609011

*The Open Fund of Gansu Resources and Environmental Science Data Engineering Technology Research Center in 2015(2015年甘肅省資源環(huán)境科學(xué)數(shù)據(jù)工程技術(shù)研究中心開放基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-11-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161107.1703.004.html

ZHOU Yang,CHEN Xiaoyun,CHENG Jianjun,et al.Bisection spectral community-detection methods using optimal eigenvectors.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1897-1906.

A

TP181

ZHOU Yang was born in 1991.He is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include community detection and complex network analysis,etc.

周旸（1991—），男，江蘇溧水人，蘭州大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)樯鐖F(tuán)檢測，復(fù)雜網(wǎng)絡(luò)分析等。

CHEN Xiaoyun is a professor at School of Information Science and Engineering,Lanzhou University,and the member of CCF.Her research interests include database,data mining and high performance computing,etc.

陳曉云，女，蘭州大學(xué)信息科學(xué)與工程學(xué)院教授，CCF會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫，數(shù)據(jù)挖掘，高性能計(jì)算等。

CHENG Jianjun is a teacher at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

程建軍，男，甘肅甘谷人，博士，蘭州大學(xué)信息科學(xué)與工程學(xué)院教師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析等。

LIU Wei is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

劉偉，男，湖北公安人，蘭州大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析等。

MIAO Haifei is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

苗海飛，男，山西山陰人，蘭州大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析等。