backstage

合唱音源の新着情報の舞台裏

Google PageRankベクトルをRubyで求めてみた

Google PageRankの数理』という本を読んでいます。 www.kyoritsu-pub.co.jp

内容は古いものの、GoogleSEO順位を定量的に算出するロジックについて解説している貴重な一冊です。 楽しいのですが線形代数学の知識を要求されるので、読むのが結構しんどい本でもあります。

PageRankをベクトルで表す

まだ最初の数十ページしか読んでいないのですが、GooglePageRankの求め方はこの本の50ページに、下記のように書かれていました。

Google行列GのPageRankベクトルはGの定常ベクトルで、次のものになる。
π = [0.03721, 0.05396, 0.04151, 0.3751, 0.206, 0.2862]
※ Gは既知の6次元正方行列(省略)

「次のものになる」とか言って突然に答えを出しているのですが、この算出方法がよく分かりませんでした。 (そもそも 定常ベクトル なんて単語は記憶に無い)

この定常ベクトルπが実際のPageRankを表しております。 6次元正方行列Gで表される6つのページに対して、最大値「0.3751」を持つ4番目のページが最もPageRankが高く、逆に最低値「0.03721」の1番目が最もPageRankが低いという事になります。

つまりこの 定常ベクトルとやらが肝 なので、求めないと話になりません。

なので実際に求めてみました。

定常ベクトルを求める

まず書籍にある定常ベクトルの定義から、1次方程式の形に変形します。

x を求めたい定常ベクトル、 GGoogle行列(各ページのリンクとかを表す行列)とすると

 x=xG  , xe=1

 \Leftrightarrow

 \begin{bmatrix}E-G \end{bmatrix}^{\mathrm{T}}x=0,  ex=1

  \Leftrightarrow


  \begin{bmatrix}
 \begin{bmatrix}E-G \end{bmatrix}^{\mathrm{T}}  \\ e
\end{bmatrix}x=
 \begin{bmatrix}0 \\ 1 \end{bmatrix}
・・・(1)

(TeXとか久しぶりすぎて何も覚えてない…)

(1)の1次方程式を解くメソッドを、Rubyのmatrixライブラリを使うことで以下のように記述します。

require 'matrix'

# 引数google: Google行列
def page_rank(google)
  dimension = google.row_size

  ans = (Matrix.identity(dimension) - google).transpose
  ans = Matrix.rows(ans.to_a.push([].fill(1,0,dimension)))
  ans = ans.lup.solve([].fill(0,0,dimension).push(1))
  ans.covector.minor(0,1,0,dimension).round(5)
end

# 書籍に記載されている実際のGoogle行列G
g = Matrix[
[1,28,28,1,1,1],
[10,10,10,10,10,10],
[19,19,1,1,19,1],
[1,1,1,1,28,28],
[1,1,1,28,1,28],
[1,1,1,55,1,1]
].map{|i| i.to_f / 60 } 

p page_rank(g)
#=> Matrix[[0.03721, 0.05396, 0.04151, 0.37508, 0.206, 0.28625]]

数学的にもプログラム的にももう少しやりようがあるような気がしますが、目的の出力は得られました。 これで無事にPageRankが求められたようです。