実際問題
……ただし、実際にPagerankを求めるにはこのままではいくつか問題があるんです。
1. ランダム・サーファ
ページを辿って情報を集める際、律儀にページ内のリンクを踏み続けるだけじゃありませんよね。ときにはまったく別のページに"テレポート"することもしばしばです。Pagerankアルゴリズムでは、85%はページ内のリンクを辿り、残る15%はでたらめにテレポートすると仮定して算出しているらしいです。
2. 袋小路
リンクを1つも持たない"行き止まり"のページがページ群に含まれていると厄介なことが起こります。今回サンプルとして用意したページ群から、ページ5から7へ向かうリンクを取り去ると、ページ5はリンクを持たないページとなります。この状態で同様の計算を行うと……。
ページ5に辿り着いたビー玉はその後の行先を失ってページ群からこぼれ落ち、ビー玉の総数が少し減ってしまいます。なのでI = H * Iを繰り返すうちに転がるビー玉がなくなってIはall-0に収束してしまうんです。
3. 堂々巡り
こんなページ群があったとします。
大きな左回りのループが見えるでしょうか。このページ群にビー玉を流し込むと、ビー玉たちは左回りに回遊し、I = H * Iを繰り返すとIの値は周期的に振動するだけでちっとも収束しません。
実際の計算では繰り返し回数の上限を定めておき、演算I = H * Iの前後でのIを比較して、その差が十分小さくなるか、繰り返し上限に達したときに計算終了とすることになるでしょうね。
4. メモリ消費量
今回のサンプルはページ数8の小さなページ群を対象としましたが、実際には数百数千それ以上のページ数になるでしょう。推移確率行列Hのサイズはページ数の二乗に比例し、1000ページで4MB、10000ページだと400MBを消費します。
ページ数8だと行列Hはfloat64個分、ですがこの行列の要素は多くが0で埋まっています（0でないのはリンク数と同じ17個）。ページ数が増えるに従って0要素の割合は増えるでしょう。推移確率行列Hはナカミがほとんど0、スカスカの行列となります。ならば疎行列（sparse matrix）として扱えば、データ量は"ページ数の二乗に比例"から"リンク総数に比例"に（劇的に）減らすことができます。
……というわけで、Pagerankを求めるアルゴリズムのキモは意外と単純。だけど実用には一筋縄ではいかないよ。というオハナシでした。
補足
CUDA Toolkit 8には実際に使えるPagerankを実装したCUDAライブラリ：nvGRAPHが同梱されています。興味のある方ゼヒお試しあれ。
