基于譜聚類的社團發現算法

徐步東

(山東師范大學 信息技術管理處，濟南 250014)

引言

現實世界中有大量的系統可以用由一些點和連接各個節點的邊組成的網絡來表示，如萬維網、食物鏈網絡。節點是表示復雜系統的基本單元，節點間的邊表示各個單元的相互作用。系統中的每個節點以及每條邊的性質都可以用稱為“權重”和“強度”的更多信息來描述。

隨著復雜網絡研究的深入，人們注意到大量的實際網絡都具有社團結構性質，即一個完整的實際網絡通常是由若干個“社團”構成。我們著力研究實際網絡的社團結構，從而有利于人們更加深入地了解網絡結構以及分析網絡的特性，使人們更加有效地理解和利用這些網絡。例如，在發現社團以及社團的邊界后我們可以根據結點的拓撲位置對結點進行分類，處于社團邊界上的結點成為社團之間聯系的橋梁，整個社團中心結點則控制著整個社團的穩定性。

1 復雜網絡中社團發現算法研究現狀

復雜網絡中社團發現算法的一個主要目標是根據整個網絡的拓撲結構來尋找網絡中所存在的社團。社團發現與復雜網絡的層次聚類和計算機科學圖論中圖分割的思想密切相關。層次聚類方法主要分為兩類:凝聚方法(Agglomerative Method)和分裂方法(Divisive Method)。圖分割主要包括兩個算法:基于Laplacian 圖特征值的譜平分法(Spectral Bisection Method)和Kernighan-Lin 算法。

Girvan 和Newman 提出了一類優化模塊度Q 的算法，其中主要有極值優化算法以及模擬退火算法等，優化模塊度算法的時間復雜度較高。Newman 還利用網絡中一個新的特征矩陣的特征向量來重新定義了模塊度Q，我們稱這個特征矩陣為模塊度矩陣(modularity matrix)。這是一種新的譜方法，并且這種算法與直接優化Q 的算法相比時間復雜度較小。

圖分割方法很難將網絡劃分成有效數目的社團，不適用于結構未知的網絡。Girvan 和Newman 提出了模塊度，它可以有效地衡量社團劃分結果。本文提出了一種基于譜聚類的社團發現算法。實驗結果表明，通過與現有的社團發現算法比較，本文提出的算法效率更高，而且在處理結構未知的大型網絡時，得到的結果令人滿意。

2 基于譜聚類的社團發現算法

假設有一個無向加權圖G(V，E，W)，對稱矩陣W=［wij］nxn，其中n 代表圖G 中所含的節點數，wij代表連接頂點i 與j 的權值。模塊度用于判定從網絡的拓撲結構中得出的社團是否具有實際網絡的社團結構。模塊度定義表述為:假定把整個網絡劃分成g 個社團，構建一個g×g 維的矩陣b=［bij］，其中元素bij表示兩個頂點i、j 之間的邊數占總邊數中的比例，令ai=∑jbij表示與第i 個節點相連接的邊的數目占整個網絡的總邊數的比例。模塊度Q 如下式所示:

若社團內部的邊所占的比例不大于所得出的期望值，則Q=0。令Q 上限為1，Q 越接近于這個值，則網絡中的社團結構就越明顯。在現實世界的網絡中，該值通常介于0.3～0.7 之間。

本文提出了一種基于譜聚類的社團發現算法。算法描述如下:

輸入:復雜網絡G(V，E，W)，kmax和kmin(kmax設為n/3，kmin設為2)

輸出:聚類結果{V1，V2，…，Vk}

Step1:將網絡G 初始化為包含所有節點的一個整簇，同時令Q=0;

Step2:對于G 中各簇Vc

1:構造權值矩陣W=Rnxn及對角矩陣D=∑jwij;

2:計算概率轉移矩陣M=D-1W;

3:計算矩陣M 的前kmax個最大特征值及其對應的特征向量u1，u2，…，ukmax，構造矩陣Uk=［u1，u2，…，ukmax］∈RnxK，并將Uk的行向量轉變為單位向量;

4:for(k=kmin;k≤kmax;k++){

(1)將Ck中的每一行看作GK空間中的一個點，應用k-means 算法來獲得k 個新子簇，VC1，VC2，…，VCi;

(2)令G’=G，并將G＇中的Vc設置為VC1，VC2，…，VCk;

(3)計算Q(G’);}

5:選取能夠使Q(G’)值達到最大的k*，即k*=argmaxkQ(G’);

6:若Q(G’)＞Q(G)，則G 中各個簇的結構不變;否則，計算step2，對G 中其他簇計算。

該算法的時間復雜度為O(nk2

maxlogkmaxK)。若復雜網絡為稀疏網絡，則算法的時間復雜度為O(nkmaxlogkmaxK)。

3 實驗結果及分析

為了測試本文算法的效率，選用2000 年美國大學足球賽網絡、Zachary 網絡、2008 年4 月人民網的強國論壇“深入討論”板塊的數據(其中共有95，247 條數據)以及爵士樂隊，將本文基于譜聚類的社團發現算法同經典的GN、NM、MS 算法進行比較，主要比較算法的執行時間及模塊度值，結果見表1 和表2。

表1 幾種算法的模塊度值比較

表2 算法執行時間比較T/s

從表1 可以看出，本算法在四種復雜網絡中得到的社團結構均具有最高Q 值，該結果表明運用本文算法得到的社團結構更加令人滿意。從表2 我們可以看出，GN、NM 和MS 三種算法在包含幾百個節點的小網絡中能有效進行社團劃分，但節點數達到上萬后，這三種算法無法計算Q 值。本文的算法可以在相對較短的時間內處理具有上萬個節點的大型網絡。

結束語

本文針對以往社團發現算法中時間復雜度較高這一問題，提出了基于譜聚類的社團發現算法，重新定義了模塊度的衡量標準。將整個網絡看作是一個社團，通過求解模塊度矩陣的最大特征值及其對應的特征向量，借助k-means 算法，將整個網絡劃分為若干子簇，直到每個子簇不能再細分，然后輸出結果。因此，得到的社團結構具有較高的質量。實驗結果表明，本文提出的算法，能夠在相對較短的時間內，處理節點數相對較多的大型網絡并且對大型網絡的結構實現了較好的劃分，能夠有效地對社團內部結構進行發掘。

［1］Shen-Orr S，Milo R，Mangan S，Alon U.Network motifs in the transcriptional regulation network of Escherichia coli［J］.Nature Genetics，2002，(31):64.

［2］汪小帆，李翔，陳關榮.復雜網絡理論及其應用［M］.北京:清華大學出版社，2006:162-198.