復雜網絡中社團結構算法的綜述

吳 悠

（武漢理工大學，湖北 武漢430070）

0 引言

隨著對網絡性質的物理意義和數學特性的深入研究， 人們發現許多實際網絡都具有一個共同性質，即社團結構。 近年來，社團結構分析在生物學、計算機圖形學和社會學中都有廣泛的應用[2]。 目前關于復雜網絡中社團結構算法的研究有很多，本文將介紹幾種有代表性的方法。

1 Kernighan-Lin 算法

1.1 方法概述

Kernighan-Lin 算法是一種試探優化法。 它是一種基于貪婪算法原理將網絡劃分為兩個大小已知的社團的二分法。

1.2 實現過程及應用[3]

K-L 算法可以描述為：首先，將網絡的節點隨機地劃分為已知大小的兩個社團。在此基礎上，考慮所有可能的節點對，其中每個節點對的節點分別來自兩個社團。對每個節點對，如果交換這兩個節點的話，計算可能得到Q 的增益Q=Q交換前-Q交換后,然后交換最大的△Q 對應的節點對，同時記錄交換后的Q 值。 規定每個節點只能交換一次。 重復這個交換過程，直到某個社團內所有的節點都被交換一次為止。 需要注意的是， 在節點對交換的過程中，Q 值并不一定是單調增加的。 不過，即使某一步的交換會使Q 值有所下降，也仍然可能在其后的步驟中出現一個更大的Q 值。 當交換完畢后，便找到上述交換過程中所記錄的最大Q 值。 這時對應的社團結構就認為是該網絡實際的社團結構。

1.3 評價

該方法存在一個嚴重的缺陷，即必須事先知道該網絡的兩個社團大小分別是多少，否則就很可能不會得到正確的答案。 K-L 算法的這個缺陷使得它在實際網絡分析中難以應用。 而且，即使解決了這個問題，它仍然面臨著如何事先知道網絡社團數目，以確定二分法要重復到哪一步停止的問題。

2 譜平分法

2.1 方法概述

該算法利用網絡結構的Laplace 矩陣中不為0 的特征值所對應的特征向量和同一個社區內的節點對應的元素近似值相等的原理對網絡社區進行劃分。

譜平分法本質上是一種二分法，在每次二分的過程中，網絡被分割成兩個近似平衡的子網絡。 當網絡中含有多個社團時，譜平分法遞歸地分割現存的子網絡，直到滿足預先定義的停止條件為止。

2.2 實現過程

該算法可以描述為：一個有n 個節點的無向圖G 的Laplace 矩陣是一個n×n 維的對稱矩陣L。 如果節點i 和節點j 有邊相連，則lij=-1，否則lij=0.對角線上的元素lij表示節點i 的度。 由于Laplace 矩陣所有的行或列的和都為0，因此，該矩陣總有一個特征值為0，且其對應的特征向量為I=（1，1，1,···，1）。 我們也可以將矩陣L 表示成L=K-A，其中K 是一個對角矩陣，其對角線上的元素對應各個節點的度，而A則為該網絡的連接矩陣。 可以從理論上證明，不為零的特征值所對應的特征向量的各元素中，同一個社團內的節點對應的元素是近似相等的。 因此，可以根據復雜網絡的Laplace 矩陣次小特征值λ2對應的特征向量，所有正元素對應的那些節點都屬于同一社團，而所有的負元素對應的那些節點都屬于另一個社團，這樣就將其分為兩個社團。

2.3 評價及改進方法

譜平分法主要缺陷是只能將圖分成2 個子圖， 若要分成多個子圖，則只能多次應用該方法。即使這樣可行，我們預先也無法確定究竟將圖分割成多少個子圖才合適。

為了克服這一缺陷，Capocci 等人在傳統譜分析法的基礎上提出另一種算法。 傳統譜平分法是基于Laplace 矩陣L=K-A。Capocci 算法[4]則是基于標準矩陣N=K-1A。 利用行標準化的轉換可得，矩陣N 的最大特征值總是等于1，相應的特征向量稱為平凡特征向量。 在對社團化明顯的網絡的分析中發現，如果網絡自然呈現g 個社團，則標準矩陣就有g-1 個十分接近1 的第一非平凡特征值，而其余的特征值都與1有較大的距離。 這g-1 個特征值所對應的特征向量（稱為第一非平凡特征向量或者第二特征向量）有一個特性：在同一個社團中的頂點所對應的值較為接近。因此，特征向量中元素的值呈現階梯狀分布，并且階梯的級數與社團的個數相匹配。

3 GN 算法

3.1 方法概述

Girvan 和Newman 提出了一種基于邊介數的分裂算法，即G-N 算法。 不斷地從網絡中移除介數最大的邊。 邊介數定義為網絡中經過每條邊的最短路徑數目。

3.2 實現過程

首先，計算網絡中各條邊的邊介數，找出邊介數最大的邊，并將它移除（如果最大邊介數的邊不唯一，那么既可以隨機挑選一條邊斷開也可以將這些邊同時斷開）；然后，重新計算網絡中剩余各條邊的邊介數；接著重復上面的步驟，直到網絡中所有的邊都被移除。

3.3 評價及改進方法

GN 算法彌補了一些傳統算法的不足，但是也存在一個缺陷，即它對于網絡的社團結構并沒有一個量的定義。因此不能直接從網絡的拓撲結構判斷它所求得的社團結構是否是實際網絡中的社團結構，從而需要一些附加的關于網絡意義的信息來判斷所得到的社團結構是否具有實際意義。

為了得到具有實際意義的社團結構，Newman 等人引進了一個衡量網絡劃分質量的標準——模塊度。 考慮某種劃分形式，它將網絡劃分為k 個社團。 定義一個k×k 維的對稱矩陣E=（eij），其中元素eij表示網絡中連接兩個不同社團的節點的邊在所有邊中所占的比例，這兩個節點分別位于第i 個社團和第j 個社團。

4 結束語

復雜網絡中社區的劃分具有重要的使用價值。本文給出了三種經典的復雜網絡社團劃分算法，較為詳細的描述了各種算法的核心思想和基本過程，并對各算法進行了適當的分析和比較，為影虎針對不同的復雜網絡選擇適合的社區劃分算法提供了一定的借鑒作用。

［1］韓瑞凱，孟嗣儀.基于興趣相似度的社區結構發現算法研究[J].鐵路計算機應用，2010,19（10）：10-14.

［2］張聰，沈惠璋.復雜網絡中社團發現的快速劃分算法[J].系統工程，2011,29（208）：93-98.

［3］汪小帆，劉亞冰.復雜網絡中的社團結構算法綜述[J].電子科技大學學報，2009,38（5）：537-543.

［4］謝福鼎，張磊.一種基于譜平分法的社團劃分算法[J].計算機科學，2009,36（11）：186-188.

［5］安娜，謝福鼎.一種基于GN 算法的文本概念聚類新方法[J].計算機工程與應用，2008,44（14）：142-144.