RookieTraining-PageRank

グラフファイルの形式

グラフファイルは毎度お馴染みの形式で。pagerank.cppの #define GRAPH_FILE "simple.digraph" で定義してください。

例として、simple.digraph は以下です。

1 2
1 3
2 3
3 1
3 4
3 5
5 6
6 5

実行

以下で実行されます。

g++ pagerank.cpp -o ./pagerank
./pagerank

出力はノード ID と その PageRank です。例としてsimple.digraph を用いれば、

% ./pagerank
1: 0.051147
2: 0.047574
3: 0.090044
4: 0.051563
5: 0.38698
6: 0.372692

のように出力されます。

やってみた感想

p2p-Gnutella04.txt （10876ノード、39994エッジ）で1000万ステップすると10秒くらい。1億ステップすると1分34秒でした。

NetworkX のライブラリで計算した PageRank では、（python3 pagerank.pyで実行できます）たとえば最後の3つは

10876: 5.7483912987066724e-05
10877: 0.00010514421409400435
10878: 7.211287900179118e-05

だった一方で、わたしの実装で計算した最後の3つは

10876: 5.76e-05
10877: 0.00010575
10878: 7.168e-05

となり、「うーん」ぐらいな印象。しかも NetworkX の方は実行時間が10^-1秒オーダーくらい。

ランダムウォークを初めて実装したので細かいスピードアップは出来ると思います（特にランダム値の生成あたり）。しかし、1億ステップやってこの精度ってことなので、かなり効率の悪い方法のように感じられました。ランダムウォークってこんなもん？って印象。