Loading article…
Girvan –Newmanアルゴリズム（Michelle GirvanとMark Newmanにちなんで名付けられた）は、複雑なシステムにおけるコミュニティを検出するために使用される階層的な手法である。[ 1 ]
ガーバン・ニューマンアルゴリズムは、元のネットワークからエッジを段階的に削除していくことでコミュニティを検出します。残ったネットワークの連結成分がコミュニティとなります。コミュニティの中心となるエッジを特定する指標を構築しようとするのではなく、ガーバン・ニューマンアルゴリズムは、コミュニティ間に位置する可能性が最も高いエッジに焦点を当てます。
頂点媒介中心性は、ネットワークにおける中心性の高いノードを示す指標です。任意のノードについて頂点媒介中心性とは、ノード間の最短経路のうち、その頂点を通過する経路の割合として定義されます。これは、ネットワークが既知の始点と終点間の商品の輸送を調整するモデルにおいて重要であり、そのような輸送は利用可能な最短経路を追求するという仮定に基づいています。
ガーバン・ニューマンアルゴリズムは、この定義をエッジの場合に拡張し、エッジの「エッジ媒介中心性」を、そのエッジに沿って走るノードペア間の最短経路の数として定義します。ノードペア間に複数の最短経路がある場合、すべての経路の合計重みが1になるように、各経路に等しい重みが割り当てられます。ネットワークに、少数のグループ間エッジによって緩やかに接続されているコミュニティやグループが含まれている場合、異なるコミュニティ間のすべての最短経路は、これらの少数のエッジのいずれかに沿う必要があります。したがって、コミュニティを接続するエッジは、高いエッジ媒介中心性（少なくとも1つ）を持ちます。これらのエッジを除去することで、グループが互いに分離され、ネットワークの根底にあるコミュニティ構造が明らかになります。
コミュニティ検出のためのアルゴリズムの手順を以下にまとめます。
再計算される媒介中心性は、削除によって影響を受けるものだけであるため、コンピュータ上でのプロセスシミュレーションの実行時間を短縮できる可能性があります。しかし、媒介中心性は各ステップで再計算する必要があり、そうしないと重大なエラーが発生します。その理由は、ネットワークがエッジ削除後に設定された新しい条件に適応するためです。たとえば、2つのコミュニティが複数のエッジで接続されている場合、これらのエッジすべてが高い媒介中心性を持つとは限りません。この方法によれば、少なくとも1つのエッジが高いことはわかっていますが、それ以上のことはわかりません。各エッジの削除後に媒介中心性を再計算することで、2つのコミュニティ間の残りのエッジのうち少なくとも1つが常に高い値を持つことが保証されます。
ガーバン・ニューマンアルゴリズムの最終結果はデンドログラムです。ガーバン・ニューマンアルゴリズムの実行中、デンドログラムは上から下へと生成されます（つまり、リンクが順次削除されることでネットワークが異なるコミュニティに分割されます）。デンドログラムの葉は個々のノードです。
