Girvan-Newmanのコミュニティー分割アルゴリズムをNetworkXでやってみた

Pythonの複雑ネットワーク解析ライブラリーであるnetworkXを使って、Girvan-Newman algorithmのコミュニティー分割をしてみました。

分割されていく様子をgifアニメーションにしています。

f:id:millionsmile:20120909114250g:plain

Girvan-Newman algorithmは、あるコミュニティーの中で媒介中心性の高いエッジ（リンク、繋がり）を検出し、そのエッジを切ることで、そのコミュニティーを分割していくアルゴリズムです。

原論文はこちら（PDFをリンクしています）。

Girvan, M., Newman, M. E. J., Community structure in social and biological networks", Proceedings of the National Academy of Science of the United States of America, Vol. 99, pp. 7821-7826 (2002)

データはZachary's karate club（ある海外の大学で空手クラブで２人のリーダーが仲間割れしたときの内部の人間関係ネットワーク）を使っています。データ・ソースは、Network dataから取得できます。

ノードID = 33 (空手クラブの主将)とノードID = 1 (パートタイムのインストラクター)が空手クラブの経営問題を巡って対立した時の中心メンバー34人の友人関係です。

f:id:millionsmile:20120909150437p:plain

ここでは媒介中心性の高いエッジを切っていくわけなので、主将派とインストラクター派をつなぐ役割を果たしているエッジが最初に切られます。さらに分割されたコミュニティー内で媒介中心性の高いエッジを切っていく、というのを繰り返していきます。

最終的には空手クラブのネットワークは、70回分割にかけたところで、きれいに分割されました。

媒介中心性の計算式はこちら。

$b_{i}\equiv \frac{ \sum_{i_{s}=1;i_{s}\neq{i}}^{N} \sum_{i_{t}=1;i_{t}\neq{i}}^{i_{s}-1} \frac{g_{i}^{(i_{s}i_{t})}}{N_{i_{s}i_{t}}} } {(N-1)(N-2)/2}$

$g_{i}^{(i_{s}i_{t})}$ は、ある頂点 $v_{i_{s}}$ から別の頂点 $v_{i_{t}}$ へ行く最短経路の中で $v_{i}$ を通る数で、 $N_{i_{s}i_{t}}}$ は $v_{i_{s}}$ から $v_{i_{t}}$ へ行く最短路の総数である。分子は頂点 $v_{i}$ が他の点を結ぶ最短路上にあると得点が入る。分母は規格化定数である。

コードはこちら。

今回は媒介中心性を使いましたが、この手法でコミュニティ分割する場合、計算量が大きいとか、どこまで分割するべきなのかといった数値を予め設定しなければいけないなどの欠点があり、アルゴリズムの改良が進んでいます。最近では、媒介中心性ではなく、モジュラリティQというコミュニティ分割結果の良さの指標というのが考えだされています。モジュラリティQに関してはまた別の機会に試してみます。

※元ネタは2008年に書かれた「tsubosakaの日記」の記事より。今のPythonのバージョンだとライブラリの階層が変更になっていたりして動かないのでそこを改良しています。

※参考文献『複雑ネットワーク -基礎から応用まで-』増田直紀、今野紀雄著