格文-紐曼算法

格文-紐曼算法（得名於米歇爾·格文和馬克·紐曼）是複雜系統啟發式社區發現算法。

邊介數和社會結構

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

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

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

格文-紐曼算法的步驟如下：

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

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