Girvan–Newman算法

來自維基學院

Girvan–Newman算法(以Michelle Girvan和k Newman的名字命名 )是複雜系統中一種啟發式的社區發現算法,本文旨在說明該算法的一部分特性。

邊介數和社會結構[編輯 | 編輯原始碼]

Girvan-Newman算法通過不斷地刪除網絡中的邊來檢測網絡中的社區。在最終剩餘的網絡中的連通分量也就是社區。Girvan-Newman算法並不是去測量哪些邊具有最高的中心度,而是去關注哪些最有可能連接著社區。

頂點介數是一種反應網絡中頂點的中心度的指標。對於一個頂點i,頂點介數是指網絡中經過該頂點的所有最短路徑的數量。

Girvan-Newman算法將介數擴展到了邊。類似地,一條邊的邊介數是指網絡中經過該邊的最短路徑的數量。如果一個網絡所包含的社區之間是由少量的邊連接的,那麼經由不同社區的最短路徑都需要從這些邊上經過,因此這些邊的邊介數會非常高。通過移除這些邊,各個社區之間將會被分割開來,從而可以發現這些社區。

Girvan-Newman算法的步驟如下:

重新計算剩餘每條邊的邊介數需要不少計算時間,然而,並沒有較好的辦法省去這些開銷。當一條邊被刪除了之後,網絡的結構發生了變化,舉個例子來說,假設兩個社區之間有不止一條邊連接,那麼並不是每條邊都會有較高的邊介數,我們只能逐漸地刪除這些邊,在這個過程中會發現至少有一條邊會有較高的邊介數。

Girvan-Newman算法的結果是一個樹狀圖。這個樹狀圖自頂向下地描繪了社區的結構。樹狀圖的葉子則是圖的每個結點。