Page Rankの近似推定

#前書き
本稿ではpage rankというアルゴリズムの大まかな概念と，行列演算を用いた近似推定について述べています．
また，最後にアルゴリズムをpythonで実装(20行程度)しています．

#Page rankとは
web pageにおけるrank付けを行うアルゴリズム
page rankによって定まるrankが高いほど検索時に上位になる
http://ja.wikipedia.org/wiki/ページランク

• リンクされている（他ページによってそのページヘのリンクがはられている) 場合，pagerankは加算される．
• 多くリンクされているページ（pagerankが高いページ）からのリンクのほうがpagerankはより加算される．
• 複数のページヘのリンクがある場合，すべてのページに対し同等のpagerankが加算される．

大体こんな感じ

#求め方
ここでは実際のweb pageのpagerankを求めるのではなく，用意したpage群(有向グラフ)におけるpagerankを求めます．

有向グラフの例
-存在するページ数：6
page1 → page3, page5
page2 → page3
page3 → page5, page6
page4 → page1
page5 → page2, page4, page6
page6 → page1

###隣接行列
まずグラフから隣接行列を考えます．
行に対し上からpage1, page2 ...　と考えたときの隣接行列は

\begin{pmatrix}
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}

行が現在のpage, 列がつながっているpageを示しています．
どこへのリンク（すなわち隣接しているか）がわかるようになっています
例えば5行目なら page5はpage2,4,6へのリンクがあると読み取ることができます．

###遷移確率行列
次にこれを遷移確率行列にします．
まず一度転置します(ホントは最初から転置したものを考えるとか効率いい考えがあります）

\begin{pmatrix}
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
\end{pmatrix}

転置したものを列ごとに見て，列ごとの総和が1になるようにします．

\begin{pmatrix}
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1/3 & 0 \\
1/2 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1/3 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 1/3 & 0 \\
\end{pmatrix}

まず転置したので，列は現在のpage, 行はつながっているpageを示しています．
あるページにn個のpageへのリンクがある場合，すべてのpageに同等のpagerankを与える　
→　それぞれのpageへ移動する確率が 1/n
と考え，列ごとの総和が1になるようにしています．

要するにpage1にいるときpage3に遷移する確率は1/2, page5に遷移する確率は1/2
と考えています．

###ランダムウォーク
後は遷移確立行列に従って，n回後の存在確率を計算します．
このnが大きければ大きくなるほど答えが収束していくため，近似的にpageのrankを求めることができます．

まず初期ベクトルを与えます

\begin{pmatrix}
0 \\ 
1 \\
0 \\
0 \\
0 \\
0\\
\end{pmatrix}

これはどこに1があってもいいです
要するに最初にどのpageにいるかということです．

後は先ほどの遷移確立行列とこの初期ベクトルの内積をとれば，現在の存在確率の行列(なんて呼ぶのかしらない）が出ます．
さらにそこに遷移確率行列をかけていくことできます．

\begin{pmatrix}
0 \\ 
1 \\
0 \\
0 \\
0 \\
0\\
\end{pmatrix}
\begin{pmatrix}
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1/3 & 0 \\
1/2 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1/3 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 1/3 & 0 \\
\end{pmatrix}

#ソースコード
最後にpython(多分2.7)での実装例を書いておきます．

pagerank.py

import numpy as np
import time

x = np.array([
[0, 0, 1, 0, 1, 0],                                                                              
[0, 0, 1, 0, 0, 0], 
[0, 0, 0, 0, 1, 1], 
[1, 0, 0, 0, 0, 0], 
[0, 1, 0, 1, 0, 1], 
[1, 0, 0, 0, 0, 0]],
dtype=float)
pagenum = 1 
pagerank = 30
rank = np.array([[0],[1],[0],[0],[0],[0]])

x_m = x.T/x.T.sum(axis=0)

for i in range(100000):
    rank = np.dot(x_m, rank)

print(x)
print(np.round(rank * pagerank/rank[pagenum - 1],2))

xの変数定義では隣接行列を書きます．
また，この手法ではpage間のrank比率が出るのみなので，実際には基準となるrankが分かっている必要があります．
よって
pagenumに基準となるpageの番号
pagerankにpagenumのrankを書いて
後は動かせば終わりです．

10万回内積をとっていますが自分の環境では計算時間は400ms程度でした．