読者です 読者をやめる 読者になる 読者になる

RubyでPageRankアルゴリズムを実装する


みなさんご存知、Webページ重要度の自動判定アルゴリズムであるPageRankですが、この記事

PageRankアルゴリズムを使った人事評価についての実験 | 株式会社サイバーエージェント

を読んで、PageRankアルゴリズムを身の回りのさまざまなリンク構造を持ったデータに対して適用してみたいなぁと思い、実装してみました。Rとかで既存のライブラリを使って、データを入れたら結果だけが返ってきて、中でどんな計算してるかは知らない、みたいなのは何も理解したことにならないので、実際にアルゴリズムを調べて実装し、どんな計算をしているのかまで理解するためにやりました。

f:id:hongo35:20131118025952p:plain


PageRankアルゴリズム

PageRankアルゴリズムは、「たくさんの良質なページからリンクされているようなページは、やはり良質なページである」という再帰的な関係をもとに、あらゆるページの重要度を計算したもので、引用に基づく学術論文の評価と似たアルゴリズムです。このアルゴリズムのポイントとしては、以下の3点が挙げられます。


1. 重要な論文はたくさんの論文から引用されるので、被引用数が多くなる

 → 重要なWebページはたくさんのページからリンクされるので、被リンク数が多くなる

2. 被引用数の多い論文から引用されている論文は、重要度が高い

 →被リンク数の多いページからのリンクは価値が高い

3. 多くの論文を引用している論文からの引用は価値が低い

 → リンク元ページのリンク数が多いページからのリンクは価値が低い

(ページランク - Wikipediaより引用)


数学的に注意しなければいけないことは、ランダムウォーク(マルコフ連鎖)がエルゴード性(集合平均と時間平均が一致するという性質)を満たす必要があるということです。 そのエルゴード性を満たすためにテレポーテーションを導入します。つまり、

・確率αで, 今いるページにあるリンクを一つ等確率で選ぶ

・確率1 - αで、でたらめなページ(等確率で)にテレポート

という実装をします。そして、Rubyで実装したものがこちら。

gist7513104

実行結果

----------
alpha: 1.0
[0.16666674613952637, 0.27777934074401855, 0.33333325386047363, 0.22222065925598145]
----------
alpha: 0.8
[0.1785715084624, 0.2704091523808, 0.3214284915376, 0.22959084761919998]
----------
alpha: 0.5
[0.20000008174320807, 0.26000069598110753, 0.29999991825679195, 0.23999930401889247]
----------
alpha: 0
[0.25, 0.25, 0.25, 0.25]

参考資料で実装されているものと結果が同じになったので、これでおkかと。 一般的には、ダンピングファクターの値(コード中のalpha)は0.85くらいにします。

あとはTwitterのフォロー・フォロワーネットワークとかから行列データを作って、PageRankを実行してみたいなと思ってます。 それについてはまたこんど。


参考資料

Google の秘密 - PageRank 徹底解説

リンク解析とか: 重要度尺度と von Neumann カーネル

リンク解析と周辺の話題