text: 格文-紐曼演算法是複雜系統啟發式社群發現演算法。邊介數和社會結構.格文-紐曼演算法透過不斷地刪除網路中的邊來檢測網路中的社群。在最終剩餘的網路中的連通分量也就是社群。格文-紐曼演算法並不是去測量哪些邊具有最高的中心度，而是去關注哪些最有可能連線著社群。頂點介數是一種反應網路中頂點的中心度的指標。對於一個頂點i，頂點介數是指網路中經過該頂點的所有最短路徑的數量。格文-紐曼演算法將介數擴充套件到了邊。類似地，一條邊的邊介數是指網路中經過該邊的最短路徑的數量。如果一個網路所包含的社群之間是由少量的邊連線的，那麼經由不同社群的最短路徑都需要從這些邊上經過，因此這些邊的邊介數會非常高。透過移除這些邊，各個社群之間將會被分割開來，從而可以發現這些社群。格文-紐曼演算法的步驟如下：重新計算剩餘每條邊的邊介數需要不少計算時間，然而，並沒有較好的辦法省去這些開銷。當一條邊被刪除了之後，網路的結構發生了變化，舉個例子來說，假設兩個社群之間有不止一條邊連線，那麼並不是每條邊都會有較高的邊介數，我們只能逐漸地刪除這些邊，在這個過程中會發現至少有一條邊會有較高的邊介數。格文-紐曼演算法的結果是一個樹狀圖。這個樹狀圖自頂向下地描繪了社群的結構。樹狀圖的葉子則是圖的每個結點。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 格文-紐曼演算法
metadata: https://zh.wikipedia.org/wiki?curid=6476040