RubyでPageRankアルゴリズムを実装する
みなさんご存知、Webページ重要度の自動判定アルゴリズムであるPageRankですが、この記事
PageRankアルゴリズムを使った人事評価についての実験 | 株式会社サイバーエージェント
を読んで、PageRankアルゴリズムを身の回りのさまざまなリンク構造を持ったデータに対して適用してみたいなぁと思い、実装してみました。Rとかで既存のライブラリを使って、データを入れたら結果だけが返ってきて、中でどんな計算してるかは知らない、みたいなのは何も理解したことにならないので、実際にアルゴリズムを調べて実装し、どんな計算をしているのかまで理解するためにやりました。
PageRankアルゴリズム
PageRankアルゴリズムは、「たくさんの良質なページからリンクされているようなページは、やはり良質なページである」という再帰的な関係をもとに、あらゆるページの重要度を計算したもので、引用に基づく学術論文の評価と似たアルゴリズムです。このアルゴリズムのポイントとしては、以下の３点が挙げられます。
１. 重要な論文はたくさんの論文から引用されるので、被引用数が多くなる
→ 重要なWebページはたくさんのページからリンクされるので、被リンク数が多くなる
２. 被引用数の多い論文から引用されている論文は、重要度が高い
→被リンク数の多いページからのリンクは価値が高い
３. 多くの論文を引用している論文からの引用は価値が低い
→ リンク元ページのリンク数が多いページからのリンクは価値が低い
(ページランク - Wikipediaより引用)
数学的に注意しなければいけないことは、ランダムウォーク(マルコフ連鎖)がエルゴード性(集合平均と時間平均が一致するという性質)を満たす必要があるということです。 そのエルゴード性を満たすためにテレポーテーションを導入します。つまり、
・確率αで, 今いるページにあるリンクを一つ等確率で選ぶ
・確率1 - αで、でたらめなページ(等確率で)にテレポート
という実装をします。そして、Rubyで実装したものがこちら。
実行結果
---------- 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]
参考資料で実装されているものと結果が同じになったので、これでおｋかと。 一般的には、ダンピングファクターの値(コード中のalpha)は0.85くらいにします。
あとはTwitterのフォロー・フォロワーネットワークとかから行列データを作って、PageRankを実行してみたいなと思ってます。 それについてはまたこんど。
参考資料
