ページランクのアルゴリズムをC++で試してみる

「Googleは、いかにして乾草の山から針を見つけるか」

　前回Google Mockを紹介したこともあって、Googleがらみのトピックを探していたところ、"How Google Finds Your Needle in the Web's Haystack：GoogleはどうやってWebの干草の山から針を見つけ出すのか"というタイトルの解説記事に辿り着きました。Googleでの検索結果は有用な（あるいは人気のある）ページが検索リストの上位に並びます（広告云々は別として）。各ページの有用さの度合いを計算し、それをキーに並び替えを行っているのでしょう。この記事では"有用さの度合い"をどうやって算出しているのかを解説していました。今回はこの記事をさらに噛み砕き、C++コードで実際に算出しながらの解説を試みます。

• 前回の記事『Google Mock：はじめの一歩』
• 『How Google Finds Your Needle in the Web's Haystack』

ページ群のグラフ表現

　Webページの有用さ（人気）の度合いを以降Pagerankと呼ぶことにします。Pagerankの大きなページほど有用あるいは人気があるってことで。各ページのPagerankを算出し、大きい順に並べれば役に立つであろうページほどリストの上位に並びます。

　ここでいくつかの（おそらく合理的な）推測をしておきます。

1. 有用／人気のページほど他の多くのページからリンクされている。

　それはそうでしょうね、何の役にも立たないページにわざわざリンクを張ることはないでしょうし、役立つと思うからこそリンクを張って参照／紹介するのですから。被リンク数はPagerankを決める大きなファクタであることは間違いなさそうです。

2. 有用なページから張られたリンク先のページもまた有用である。

　これも納得できます。有用なページには多くの人が訪れるので、そこから張られたリンクを辿る人もそれだけ多くなりますから。裏返せば有用でない（人気のない）ページからの多くのリンクを集めていても、そのページの有用度には疑問があるってことで。

3. 多くのリンクが1つのページから張られていると、リンクの持つ"重み"は小さくなる。

　でしょうね。たくさんのリンクを持ったページがあったとき、そこからリンクを辿った先はリンクが多いほどバラけますから、これも納得できます。

　ここでサンプル：大量のページ群から特定のキーワードを含むページを拾い上げたところ、8つのページが見つかりました。

fig01

　丸はページ、矢印はリンクを表しています。例えばページ0からページ1と2へ、ページ6からはページ4、7、0へのリンクが張られています。これら8つのページとそれ以外のページとのリンクは除外しています。対象としているキーワードを含まないページへの／ページからのリンクは気にしないってことです。対象キーワードを含んだページ群の中での順位付けなので。

　ここで推測3「たくさんのリンクを持ったページからのリンクは有難味が薄い」により各リンクに重みを付けます。例えばページ0からはページ1と2へ、計2本のリンクが張られているのでそれぞれのリンクの重みを1/2としましょう。とあるページに辿り着いた人がそれぞれのリンクを辿る確率と言えますね。とあるページからL本のリンクが張られているなら、それらリンクの重みを1/Lとする、と。当然ながらそれらリンクの重みの合計は1になります。

　このルールで各リンクに重みを付けたグラフがコチラ。

fig02

　有用なページがどれか、まだ分かりません。推測1「たくさんのリンクが飛び込むページは有用」なんだから、飛び込むリンクの重みを足し合せ、合計値が大きなページが有用なのでしょうか。

　……そうでもなさそうです。推測2「有用なページからリンクされたページもまた有用」が考慮されていないんです。人気のないページからのリンクをかき集めても人気上昇には寄与しないでしょうからね。