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

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

#方法

データの準備

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

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

ジョブの実行

ジョブ実行方法の詳細はこちらを参照。

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を送っている。

今回は下記の手順で分析結果を確認する。
(1)出力されるデータをこのスクリプトでnetworkxで読み込めるjson形式に変換する。
(2)このスクリプトでmatplotlib.pyplotでグラフ出力する
(3)このスクリプトでmodularity(Q値)も計算する。

結果

Sotera－DGAによる結果

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

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

ファイルの内容はこちら。
途中経過のデータからデンドログラムを作ることもできそう。
いったんgiraph_[0-1]のデータをもとに、最上位のグルーピング結果を作る。
データ形式については前回の資料を参照。

これをこのスクリプトでnetworkxで読み込めるjson形式に変換し、このスクリプトでmatplotlib.pyplotでグラフ出力すると下記の通りだった。

なお、Q値を計算すると0.409681130835だった。

python-louvainによる結果

karate_clubのデータをpython-louvainのbest_pertitionで解析した結果は下記のとおり。

なお、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法はノードが所属するグループが変化しなくなったら終了だったはず。）

なお、本パラメータはソースのここの処理終了判定で使用されているが、処理が途中で終わらないようにprogress.triesを10000などにするとpython-louvainと同じ結果が得られた。

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と同等の解析結果を得る手段もわかったので、次回はもっと大きなデータで検証してみたい。