PageRankの再帰回数

10数回程度の反復数で十分そう。10回程度で収束状態の7,8割の精度が達成されるらしい。

以下、参照元URLと原文の一部抜粋。

http://www.kentmiyajima.com/document/pagerank.pdf

4.4.2 収束判定基準の変更による効率化
べき乗法の収束判定基準を見直すことで PageRank 値の計算を高速化する手法を紹介
する。べき乗法による PageRank ベクトルの計算では、k 回目の反復時点の PageRank
ベクトル tr(k) と k + 1 回目の反復時点の PageRank ベクトル tr(k+1) の成分の差
の合計||tr(k+1) − tr(k)||1 が収束判定基準 ϵ を下回れば、PageRank ベクトルが収束した
（定常状態に達した）と判定していた。
Haveliwala は、PageRank ベクトルの計算において、必ずしも真の PageRank 値を
求める必要がないことに着目した [26]。PageRank 値はその相対的な大きさによって
Web ページの順位付けを行うための値であるため、正確な順位付けさえ可能であれば、
PageRank 値の近似値を算出できた時点で収束したと判定すればよいという考えを提示した。
Haveliwala は、収束判定基準の見直しによる PageRank 値の計算の高速化の可能性が
あることを実験により示している [26]。まず、べき乗法の反復を 5 回・10 回・25 回・50
回・100 回行って PageRank 値を算出し、それらの用いて Web ページの順位付けを行っ
ている。次に、反復を 100 回行って求めた PageRank 値による順位付けと、反復を 5 回・
10 回・25 回・50 回行って求めた PageRank 値の順位付けとの類似度*67を求めている。
クエリによる差はあるが、10 回程度の反復でも 7～8 割程度の正確な順位付けができるこ
とがグラフ [26] から読み取れる。Haveliwala はこの結果を受けて、収束判定基準の見直
しにより、PageRank 値計算にかかる時間を短縮することができる可能性があると述べている。