hadoop(giraph)で動作する分散グラフ分析器 sotera-DGAの動作検証(修正版)

#目的
　[前回の記事](http://qiita.com/k_ishi/items/6ea2d4cce090e47b374a)で「分散グラフ分析器 sotera/distributed-graph-analytics(以下Sotera-DGA)」のlouvain法のサンプルを実行してみたが、結果の妥当性が分からなかったので、各所でよく使われているpython-louvainの出力結果と比較検証してみる。

#方法
## データの準備
 検証用のデータとしてソーシャルネットワークの研究でよく使用されているkarate clubを使用する。
下記のコードでSotera-DGA用のフォーマットで出力する。

```python:karate.py
import networkx as nx
graph=nx.karate_club_graph()
for edge in graph.edges():
    print str(edge[0]+1) + "," + str(edge[1]+1)
```

上記コードで出力されたデータ[karate.csv](https://gist.github.com/ken57/fe264d3f5d25415c4158ea62c8c519c3)

## ジョブの実行
ジョブ実行方法の詳細は[こちら](http://qiita.com/k_ishi/items/6ea2d4cce090e47b374a)を参照。

```bash
hadoop fs -put karate.csv /user/hdfs/input
bin/dga-yarn-giraph louvain "/user/hdfs/input/karate.csv" "/user/hdfs/output" -ca io.edge.reverse.duplicator=true -ca minimum.progress=0
```
Sotera-DGAでは双方向接続のグラフでなければlouvain法を適用できず、ジョブが失敗する。パラメータ `ca io.edge.reverse.duplicator=true`をつけると、karate.csvのように単方向のノード接続しか記述されていないデータが、双方向接続されているものとみなされて読み込まれる。
パラメータ`-ca minimum.progress=0`はデフォルト値。指定しないと、値の設定部分にバグがあり2000とかいうわけのわからない値になって解析が途中で終わってしまうので、[修正のpull-req](https://github.com/Sotera/distributed-graph-analytics/pull/90)を送っている。

今回は下記の手順で分析結果を確認する。
(1)出力されるデータを[このスクリプト](https://gist.github.com/ken57/92c0d2d9a2254d18ccf17e493e152ec4#file-convert_to_json-py)でnetworkxで読み込めるjson形式に変換する。
(2)[このスクリプト](https://gist.github.com/ken57/92c0d2d9a2254d18ccf17e493e152ec4#file-graph_draw-py)でmatplotlib.pyplotでグラフ出力する
(3)[このスクリプト](https://gist.github.com/ken57/92c0d2d9a2254d18ccf17e493e152ec4#file-calc_q-py)でmodularity(Q値)も計算する。

## 結果
### Sotera－DGAによる結果
Sotera－DGAでlouvain法を実行すると、解析アルゴリズムのイテレーションごとの状態が下記のように出力される。

```bash
hadoop fs -ls /user/hdfs/output/giraph_*
-rw-r--r--   1 nobody supergroup        630 2016-06-25 04:05 /user/hdfs/output/giraph_0/part-m-00001
-rw-r--r--   1 nobody supergroup        132 2016-06-25 04:06 /user/hdfs/output/giraph_1/part-m-00001
```
ファイルの内容は[こちら](https://gist.github.com/ken57/517efa279c7e370328d117d0457055bf)。
途中経過のデータからデンドログラムを作ることもできそう。
いったんgiraph_[0-1]のデータをもとに、最上位の[グルーピング結果](https://gist.github.com/ken57/517efa279c7e370328d117d0457055bf#file-best_partition-txt)を作る。
データ形式については前回の資料を参照。

これを[このスクリプト](https://gist.github.com/ken57/92c0d2d9a2254d18ccf17e493e152ec4#file-convert_to_json-py)でnetworkxで読み込めるjson形式に変換し、[このスクリプト](https://gist.github.com/ken57/92c0d2d9a2254d18ccf17e493e152ec4#file-graph_draw-py)でmatplotlib.pyplotでグラフ出力すると下記の通りだった。
![merged_karate_result.png](https://qiita-image-store.s3.amazonaws.com/0/85207/201d557b-3b2b-f245-d850-be886dada36e.png)
なお、Q値を計算すると0.409681130835だった。

### python-louvainによる結果
karate_clubのデータをpython-louvainのbest_pertitionで解析した結果は下記のとおり。
![test_fig_python_louvain.png](https://qiita-image-store.s3.amazonaws.com/0/85207/553175e2-11ae-a1cf-b005-2ea86c32b745.png)
なお、Q値を計算すると0.418803418803だった。
Sotera-DGAのほうは12番のノードがうまく分離できていないように見える。

# パラメータ調整
Sotera-DGAのLouvainRunnerには `minimum.progress`と `progress.tries`という２つのパラメータがある。
http://sotera.github.io/distributed-graph-analytics/louvain/#louvainconfig
この2つのパラメータは、Q値の変化量に応じて計算を途中で終了させるためのもので、元論文には存在しないSotera-DGAの独自のパラメータのようだ。（元のlouvain法はノードが所属するグループが変化しなくなったら終了だったはず。）

なお、本パラメータはソースの[ここ](https://github.com/Sotera/distributed-graph-analytics/blob/master/dga-giraph/src/main/java/com/soteradefense/dga/louvain/giraph/LouvainMasterCompute.java#L133)の処理終了判定で使用されているが、処理が途中で終わらないようにprogress.triesを10000などにするとpython-louvainと同じ結果が得られた。

```bash
bin/dga-yarn-giraph louvain "/user/hdfs/input/karate.csv" "/user/hdfs/output" -ca io.edge.reverse.duplicator=true -ca minimum.progress=0 -ca progress.tries=10000 
```

# まとめ
sotera-DGAによりpython-louvainと同等の解析結果を得る手段もわかったので、次回はもっと大きなデータで検証してみたい。