網絡中社團劃分算法實現與對比研究?

李新建 楊繼紅

（1.湖北中煙工業有限責任公司信息中心 武漢 430030）（2.中國人民大學附屬中學朝陽學校 北京 100028）

1 引言

人類社會中人與人的熟知關系、計算機領域中的Internet 終端設備的互連、生物領域中分子的相互作用都可以用網絡來抽象描述，網絡中的節點對應系統中的個體，網絡的邊代表個體間的相互關系。這種抽象只保留了基本結構，過濾了復雜的背景信息，有助于對網絡代表的系統內在共同特征和性質進行研究。研究發現這些網絡并非隨機網絡［1］，它們的統計特性不同于傳統的隨機網絡結構，是無尺度網絡。網絡中包含各種社團，社團是網絡中內部比較致密，外部連接比較松散的子網絡。網絡中的社團結構是有現實意義的，例如：在人際關系網中，個體有相似愛好、職業的個體常具有社團結構特點［2～3］；在科學研究中，不同社團可代表不同的研究領域［4～5］；在Internet 中，新聞、音樂，論壇內容等可被劃分為分別不同主題的社團［6～7］。合理有效地對網絡進行社團劃分有助于發現不同的主題分組，對了解整個網絡的結構、功能和特點有重要的意義［8～9］。

一般認為，網絡中社團結構是內部連接稠密而外部連接稀疏的子網絡。“稠密”和“稀疏”是定性定義，在探索網絡社團結構的過程中無法直接使用。因此，常用定量的強社團和弱社團定義。強社團的定義為［10～11］：子圖v中任何一個頂點與v內部頂點連接的度大于其與v 外部頂點連接的度。弱社團的定義：子圖v 中所有頂點與v 內部頂點的度之和大于v 中所有頂點與v 外部頂點連接的度之和。除此以外，還有派系［12］定義，是指由三個或三個以上頂點組成的全聯通子圖，即任何兩點之間都直接相連。在此基礎通過弱化連接條件可以進行拓展，形成n-派系。例如：2-派系意味著子圖中任意兩個頂點不必直接相連，但最多通過一個中介點就可以連通。3-派系是指子圖中的任意兩個頂點，最多通過兩個中介點就能連通，以此類推，隨著n 值增加，n-派系的要求越來越弱。這些定義允許社團間存在重疊：即單個頂點并非僅僅屬于一個社團，還可以同時屬于兩個及兩個以上的社團。本文關注完全相互獨立的社團結構，因此采用較為常用的基于相對頻數的社團結構定義。

在社團定義的基礎上，在復雜網絡中進行社團結構劃分的方法大致可以分為3 類：層次聚類方法、搜索方法和其他方法。層次聚類方法又可以進一步分為凝聚過程和分裂過程，它們的主要區別在于是由底向上合并還是自頂向下分解。凝聚過程：即以頂點為基礎，通過一定方法逐步凝聚，最終形成社團。主要步驟是：1）把網絡中每個節點對象都看成一個單獨的社團，網絡中有多少節點就有多少社團；2）設定某種標準衡量社團與社團間的距離和相似度；3）逐步合并這些初始社團進而形成更大的社團，直至所有節點都聚集到一個社團中，或者滿足某個終結條件停止。分裂過程采用的層次分解方法為自頂向下，與凝聚相反。搜索方法是建立逐步優化某個目標的探索過程，社團結構直接由最后的優化結果給出。代表性的方法有PageRank［13］和HIT［14］。不屬于這兩種方法的劃為其他類，代表的方法有譜方法［15］。現有方法在復雜網絡社團結構挖掘中取得一定的效果，但是在應用過程還是存在諸多問題：1）現在很多算法雖然有效，但是復雜度很高，限制了在大網絡中進行社團結構劃分的應用。2）己有方法大多需要設置一些特定的參數，這些參數需要大量的相關領域的經驗，甚至需要專家提供指導。3）很多方法需要使用大型矩陣，需要大量計算或占用的大量存儲空間。

因此本文討論PCA、K-Means 和PSO 三種原理簡單且實現高效的社團結構劃分方法。

2 社團結構劃分方法

本文討論的PCA、K-Means 和PSO 三種劃分方法均需要利用到Girvan 和Newman 定義的模塊度［6］。模塊度指網絡中連接社團結構的內部頂點的邊所占的比例與另外一個隨機網絡中連接社團結構內部頂點的邊所占比例的期望值相減得到的差值。這個隨機網絡的構造方法是：保持每個頂點的社團屬性不變，頂點間的邊根據頂點的度隨機連接。評判社團結構劃分好壞的標準是看社團內部鏈接的稠密程度和隨機連接網絡的期望水平之間的關系。如果社團結構劃分的好，則社團內部連接的稠密程度應該高于隨機連接網絡的期望水平。用Q函數定量描述社團劃分的模塊化水平：

其中Aij為網絡中連接矩陣的元素，如果i，j兩點有邊相連，Aij=1，否則Aij=0。ci為頂點i所屬的社團，若ci=cj則?(ci，cj) =1，否則為零。m 為網絡的邊數，ki為頂點i 的度。如果社團內部頂點間的邊沒有隨機連接得到的邊多，則Q 為負值，如果Q 接近1時，表明相應的社團結構劃分得很好。

2.1 PCA

PCA方法是一種從對象中提取主要信息，忽略相對次要信息的多元統計分析方法。利用該方法將一個網絡劃分為幾個不同的社團，其本質是在最大化提取網絡本身的主要信息。它是一種自底向上的方法。應用PCA 方法實現對網絡多社團的劃分可以通過對一次劃分后所得到的社團不斷重復進行二社團結構的劃分來實現。在對一次劃分所得的社團繼續劃分時，因為該社團始終是整個網絡的一部分，這樣就需要把它放到整個網絡中去考慮，而不能把它作為一個獨立的網絡來處理。可以通過按網絡的協方差矩陣中最大的特征值所對應的特征向量在各維取值的正負，將目標劃分兩個社團。劃分結果的優劣可用模塊度來衡量。在不斷重復劃分的過程中，模塊度最大的社團結構劃分狀態一般認為是網絡實際所具有的社區結構。

2.2 K-Means

假設網絡G有n個節點和m條邊。為了衡量節點傳輸信息的有效性，引入網絡效率NE 的概念。假設網絡中兩個節點之間的信息總是沿著最短路徑傳播的，則節點i和j之間的信息傳輸效率εij為它們之間最短路徑長度dij的倒數（如果節點i和j之間不存在路徑，則最短路徑長度為∞，εij=0）。

整個網絡G 的信息有效率定義為各節點對的信息傳輸有效率的平均值NE［G］，即

邊eij的信息中心度Ceij，定義為移除該邊后整個網絡的信息有效率減少的相對量，即

社團間的邊的信息中心度比社團內部邊的信息中心度大。節點i 與j 之間的邊的信息中心度越小，它們的關聯度就越大，屬于同一個團的概率就越大，兩個相鄰節點的關聯度：

非相鄰節點間的關聯度可用最短路徑上所有節點對的關聯度乘積表示。

應用K-Means方法進行社團劃分的主要思想：以最小關聯度原則選取新的聚類中心，以最大關聯度原則進行模式歸類，直到所有的節點都劃分完為止，最后根據模塊度來確定理想的社團數，即k值。

2.3 PSO

PSO 算法具有進化計算和群智能的特點，和其他進化算法相似，PSO 也是通過個體間的協作與競爭，實現復雜空間中最優解的搜索。PSO 先產生一個初始種群，種群中每個粒子都是優化問題的一個可行解，并由目標函數確定一個適應度值，種群中的粒子將追隨當前的最優粒子運動，并經過不斷進化得到最優解：在每一次進化中，粒子將追蹤兩個極值，一個是粒子本身迄今找到的最優解pbest，一個是整個種群迄今找到的最優解gbest。在劃分問題中，PSO 中每個粒子包含一個適應值f，速度和位置更新定義為粒子的移動方向v。v 是由當前網絡節點所屬社團的情況決定。初始時，網絡中的每個節點獨立為一個社團。在算法迭代過程中，粒子的移動方向v 選擇為向任意一個與該粒子所在節點有邊，且不屬于同一個社團的下一個節點移動。當粒子到達新節點后，計算新的適應值f'，若新適應值f'大于原有值f，則把新節點的社團標號標為原有節點的社團標號，否則保持不變。直到粒子運動前后模塊Q不變或者達到進化迭代數。

3 實驗

本文實驗所用的硬件環境是：CPU Intel I5-4440（3.1GHz），內存為8GB，三種方法在Windows 7 下用C#實現。

為了比較三種方法，本文設計了兩組實驗。實驗一采用的數據集是Zachary Club 數據集。20 世紀70 年代初，Wayne Zachary 觀察了美國大學空手道俱樂部成員間的人際關系，并依據俱樂部成員間平時的交往狀況建立了一個網絡。這個網絡包含34 個頂點，代表了俱樂部成員；包含了78 條邊，代表他們之間的人際關系。由于突發的原因，俱樂部管理者與俱樂部主要教師之間針對是否提高收費這一問題產生了激烈的爭論，并最終導致俱樂部分裂成兩部分。該網絡己知網絡結構，便于比較得到劃分方法的準確性。實驗二采用計算機隨機生成網絡圖，可以通過擴大社團成員規模，比較幾種算法對不同規模網絡的運行時間和正確率。

圖1 Zachary Karate Club的社團圖。圓形節點代表管理者社團，方形節點代表教師社團。

實驗結果為PCA方法的準確率為97%，錯分了第6號節點。圖2是該網絡協方差矩陣的最大特征值所對應的單位特征向量q 在各維上的數值。特征向量q 各維的數值大小一定程度反映了其所對應的網絡中節點所屬于社團的力度。

圖2 Zachary Karate Club網絡協方差矩陣最大特征值對應的單位向量在各維上的值。三角形節點代表管理者社團，圓形節點代表教師社團

K-Means 方法的結果隨k 取值的不同，劃分的社團個數與隸屬情況也不一樣。由圖3 可知，當k取2 時，Q 值最大，表明劃分為2 個社團時是最合適的。

圖3 K-Means 對Zachary Karate Club網絡中不同社團劃分數對應的Q值

PSO 在多次計算中，還存在極少數進化搜索失敗的可能，對Zachary Karate Club進行劃分時，節點10被錯誤劃分，其余的均正確。

圖4 隨機擴展網絡規模，三種方法的時間消耗與正確率。圓形代表PSO，三角代表K-Means，十字代表PCA，實線是相應方法的時間消耗，虛線是正確率。

實驗2 通過不斷擴大社團成員規模，比較三種算法對不同規模網絡的運行時間和正確率。從圖4 可以看出，PCA、K-Means 和PSO 都保持著較低的運行時間、不低于0.8的較高的正確率。其中，PCA在運行時間上表現最為突出，K-Means 次之，基于PSO 消耗時間較長。但是，PSO 在時間上的消耗可以獲得更好的正確率，在正確率方面，PSO 表現的最好，K-Means次之，PCA 最差。因此，三種方法應用場景側重點不同有關。可根據不同社團規模進行選擇。當社團規模較小，對正確率要求較高時候選擇PSO；當社團規模較大的時候，選擇PCA 會有優勢。K-Means是折中的方法。

4 結語

本文介紹了網絡中社團劃分的方法，特別針對PCA、K-Means 和PSO 三種簡潔實用的方法進行了討論，并在Chary Karate Club 網絡和人工變尺度網絡上進行社團結構探測的性能比較，證明了三種方法劃分有效性和性能特點。