【Python】PageRankアルゴリズム

May 14, 2015  

PageRankというアルゴリズム、
以前からなんとなくは知ってはいたのですが、
ランダムサーファーモデルで計算する方法を聞いて、
めちゃくちゃ賢いなこれーって思ったので実際にやってみました。

ひとまずPageRankについて調べたことを纏めます。

PageRankは基本的に次の2つの考え方でページの重要度を推定します。
・多くのページからリンクされているページの質は高い
・質の高いページからリンクされているページの質は高い

これを数学的に考えるのにランダムサーファーモデルを利用します。
ランダムサーファーモデルでは
ページのリンク関係を有向グラフとして考え、
人(サーファー)にこの有向グラフをランダムに辿らせたとき、
人が居る確率が高いページを重要とします。

まず、ページの総数をNとし、N次正方行列M
M[i][j] = ページjにいるサーファーがページiに移動する確率
と定義します。
例えばページ0にページ1とページ5へのリンクしかないとすると、
サーファーはランダムに移動するので
M[i][0]は i=1or5 のとき1/2 となりそれ以外のiでは0となります。

また、ベクトルP(t)を時刻tに各ページに人がいる確率とすると
P(0)は全ての要素が 1/N のベクトルとなり
P(t+1)はMP(t)の積を取ることで計算できます。

有向グラフが強連結のとき、この遷移を無限に繰り返すことで
Pはtに依らない一定の値に収束します。よってこのP
M P = P
の解を要素の和が1になるよう正規化してあげることにより求められます。

このPの大きさが各ページの重要度となります。

行列計算において Ax = λx を解く、というのは固有値問題と言って
色々な方法が考えられているらしいのですが、ここについては
行列計算における高速アルゴリズム
http://www.cms-initiative.jp/ja/events/0627yamamoto.pdf
こちらのページが詳しいです。
Pythonではscipy.sparse.linalg.eigsを使うと
Implicitly Restarted Arnoldi で計算してくれます。
ただ、M P = P を解くだけのためにこれらを使うのが速いのかは
勉強不足で僕もよくわかっていません。

実際のウェブページでは、ページ間の関係を有効グラフにしても
必ずしも上で述べたような強連結になるわけではありません。
そのため「一定の確率でサーファーはリンクを辿らずにランダムに移動する」
という考えを新たに導入します。その時はMにあたるものを
全ての要素が 1/N である N次正方行列Uと普通にリンクを辿る確率αを用いて
M + (1-α)U) として計算することによってPが求められます。

次の図のようなリンク関係にあるページのPageRankを
Pythonを利用して実際に計算してみます。
正しく計算できれば図の通りの値が得られるはずです。

Linkstruct2.gif

The original uploader was Gnix at English Wikipedia[GFDL or CC-BY-SA-3.0]

コードはこちら
zaburo-ch/wikipedia_analysis/master/pagerank.py

get_pagerankではScipyを用いて固有ベクトルを計算しています。
get_pagerank_simpleではもっと単純に
P(0)に何度もMをかけていき、
かける前との差が十分小さくなるまで繰り返しています。

実行結果はこんな感じです。
pagerankresult.png

図の値とかなり一致していますね!
2つの方法どちらもほぼ同じ値になっているので
get_pagerank_simpleの方法でも十分実用に足りそうです。

このエントリーをはてなブックマークに追加