Girvan–Newman算法
Girvan–Newman算法（以Michelle Girvan和k Newman的名字命名 ）是複雜系統中一種啟發式的社區發現算法，本文旨在說明該算法的一部分特性。
邊介數和社會結構
編輯Girvan-Newman算法通過不斷地刪除網絡中的邊來檢測網絡中的社區。在最終剩餘的網絡中的連通分量也就是社區。Girvan-Newman算法並不是去測量哪些邊具有最高的中心度，而是去關注哪些最有可能連接着社區。
頂點介數是一種反應網絡中頂點的中心度的指標。對於一個頂點i，頂點介數是指網絡中經過該頂點的所有最短路徑的數量。
Girvan-Newman算法將介數擴展到了邊。類似地，一條邊的邊介數是指網絡中經過該邊的最短路徑的數量。如果一個網絡所包含的社區之間是由少量的邊連接的，那麼經由不同社區的最短路徑都需要從這些邊上經過，因此這些邊的邊介數會非常高。通過移除這些邊，各個社區之間將會被分割開來，從而可以發現這些社區。
Girvan-Newman算法的步驟如下：
重新計算剩餘每條邊的邊介數需要不少計算時間，然而，並沒有較好的辦法省去這些開銷。當一條邊被刪除了之後，網絡的結構發生了變化，舉個例子來說，假設兩個社區之間有不止一條邊連接，那麼並不是每條邊都會有較高的邊介數，我們只能逐漸地刪除這些邊，在這個過程中會發現至少有一條邊會有較高的邊介數。
Girvan-Newman算法的結果是一個樹狀圖。這個樹狀圖自頂向下地描繪了社區的結構。樹狀圖的葉子則是圖的每個結點。