# Girvan-Newman algorithm Girvan and Newman が提案した分割型(divisive)コミュニティ検出アルゴリズム。コミュニティ間辺は多数の最短路が通過しやすいという直感から、edge betweenness(辺媒介中心性、全頂点対間の最短路がその辺を通過する頻度)が最大の辺を逐次除去し、除去のたびに残りの辺のbetweennessを再計算する。この逐次除去によって生成される樹形図(dendrogram)のうち、modularity が最大になる水準の分割を最終的なコミュニティ構造として選ぶ([[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] p.23-24)。 コミュニティ検出分野における転換点(turning point)と位置づけられる代表手法であり、Girvan-Newmanアルゴリズム自体は本質的に階層的クラスタリングの一種だが、類似度の低い頂点対の辺ではなくコミュニティ間辺を除去する点が伝統的な階層的クラスタリングと異なる(同 p.23)。 ## 計算量と実用上の限界 edge betweenness 版の計算量は疎グラフで O(n^3) であり、random-walk betweenness・current-flow betweenness(両者は等価)より高速で実用上良い結果を与えるが、n〜10000程度が実用上の上限とされる。重み付きグラフへの拡張は edge betweenness を重みで割ることで対応できる(Newman, 2004)(同 p.24)。 > "The algorithm of Girvan and Newman is unable to find overlapping communities, as each vertex is assigned to a single cluster." (同 p.25) ## 派生・高速化版 - Tyler et al. — 中心点の部分サンプリングによるモンテカルロ的高速化版。Wilkinson and Huberman が遺伝子共起ネットワーク・メール網へ適用した。 - Rattigan et al. — network structure index による O(m) 近似高速化版。 - Chen and Yuan — non-redundant paths のみを数える改良版。 - Holme et al. — 頂点除去版。生化学ネットワークの階層構造解析に適用。 - Pinney and Westhead — オーバーラップコミュニティに対応する頂点分割版。 - Gregory — CONGA(Cluster Overlap Newman-Girvan Algorithm)。オーバーラップ検出のための頂点分割版。 (いずれも [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] p.24-25) ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] — 本アルゴリズムを中心に扱う章。 - [[モジュラリティ]] — 樹形図から最終分割を選ぶ基準として用いられる。 - [[コミュニティ検出]] — 分割型アルゴリズムの代表例として位置づけられる。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] — Girvan and Newman による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。