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

1.蘭州大學 信息科學與工程學院，蘭州 730000

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

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

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

1.蘭州大學 信息科學與工程學院，蘭州 730000

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

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

社團檢測；譜二分法；特征值；特征向量；模塊度

1 引言

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

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

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

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

為了驗證本文提出的社團檢測方法，在7個實際網(wǎng)絡上進行了實驗，并與一些已有的社團檢測算法進行了比較。實驗結果證實，本文方法能夠有效地從網(wǎng)絡中提取高質量的社團結構。

2 方法描述

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

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

本文提出的譜二分社團檢測方法以模塊度最大化為目標。模塊度的計算公式為：

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

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

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

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

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

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

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

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

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

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

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

同樣可以快速地進行計算。

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

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

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

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

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

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

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

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

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

算法3無權網(wǎng)絡向帶權網(wǎng)絡轉換：Weight()函數(shù)

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

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

3 實驗

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

3.1 實驗設置

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

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

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

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

3.2 實驗結果

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

本文基于譜二分法，提出了一種能夠尋找最優(yōu)的特征向量，并利用該向量對網(wǎng)絡進行分裂的社團檢測算法。同時，針對無權網(wǎng)絡上的譜二分法存在的問題，利用頂點之間的公共鄰居信息，將無權網(wǎng)絡轉換為帶權網(wǎng)絡，并將基于最優(yōu)特征向量的譜二分社團檢測方法進行了適應性改造，使其能夠充分利用網(wǎng)絡的拓撲信息進行社團檢測，提高社團質量。

本文還在7個實際網(wǎng)絡數(shù)據(jù)集上進行了實驗，以驗證提出的兩個方法的有效性，并將檢測結果與另外5個相關算法的結果進行了比較。實驗結果證實，本文算法能夠有效地從網(wǎng)絡中提取出高質量的社團結構。

[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)境科學數(shù)據(jù)工程技術研究中心開放基金).

CNKI網(wǎng)絡優(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—），男，江蘇溧水人，蘭州大學信息科學與工程學院碩士研究生，主要研究領域為社團檢測，復雜網(wǎng)絡分析等。

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.

陳曉云，女，蘭州大學信息科學與工程學院教授，CCF會員，主要研究領域為數(shù)據(jù)庫，數(shù)據(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.

程建軍，男，甘肅甘谷人，博士，蘭州大學信息科學與工程學院教師，主要研究領域為數(shù)據(jù)挖掘，復雜網(wǎng)絡分析等。

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.

劉偉，男，湖北公安人，蘭州大學信息科學與工程學院碩士研究生，主要研究領域為數(shù)據(jù)挖掘，復雜網(wǎng)絡分析等。

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.

苗海飛，男，山西山陰人，蘭州大學信息科學與工程學院碩士研究生，主要研究領域為數(shù)據(jù)挖掘，復雜網(wǎng)絡分析等。