ページランクアルゴリズムをGoで実装した

弊社プロダクトへの利用を考えてページランクアルゴリズムを実装しました。

GitHub https://github.com/yukimura45z/pagerank-go

社内向けに書いたページランクアルゴリズムの解説を一応ここにも載せておきます。

ページランクアルゴリズムのやりたいこと

サイトが[latex]N[/latex]個あるとする。

サイト[latex]i\in{1,\cdots,N}[/latex]がサイト[latex]j\in{1,\cdots,N}[/latex]へのリンクを張っていない場合は[latex]A_{i,j}=0[/latex]、張っていれば[latex]A_{i,j}=1[/latex]となる[latex]A_{i,j}[/latex]を定義する。

サイト[latex]i[/latex]の得点[latex]s_i[/latex]を求めたい。

導出

サイト[latex]i[/latex]が張ってるリンクの総数は[latex]\sum_{k=1}^{N}A_{i,k}[/latex]と表せる。

サイト[latex]i[/latex]は、自分がリンク張ってるサイトに対して[latex]\frac{s_i}{\sum_{k=1}^{N}A_{i,k}}[/latex]だけ得点を与えることになる(ようするに等分)。

つまりサイト[latex]i[/latex]はサイト[latex]j[/latex]に対して

  • [latex]A_{i,j}=1[/latex]なら[latex]\frac{s_i}{\sum_{k=1}^{N}A_{i,k}}[/latex]だけ得点を与える
  • [latex]A_{i,j}=0[/latex]なら[latex]0[/latex]だけ得点を与える

ここで、[latex]\frac{0}{0}=0[/latex]であると特別にみなす(笑)と、

  • [latex]A_{i,j}[/latex]にかかわらず[latex]\frac{s_i}{\sum_{k=1}^{N}A_{i,k}}\times A_{i,j}[/latex]だけ得点を与える

と表現できる。条件わけを二値変数使って一般化する。

スコアを与えるではなくスコアを与えてもらう、という立場に逆転して考えると、自分のスコアは与えてもらったスコアの総和である。だから
[latex]s_i = \frac{A_{1,i}}{\sum_{k=1}^{N}A_{1,k}}s_1+\cdots+\frac{A_{N,i}}{\sum_{k=1}^{N}A_{1,k}}s_N[/latex]

シグマ総和記号を使って表すと

[latex]s_i = \sum_{j=1}^{N}\frac{A_{j,i}}{\sum_{k=1}^{N}A_{j,k}}s_j[/latex]

こうなる。

これを行列で表すと

[latex]\left(\begin{matrix}s_1 & \cdots &s_i & \cdots & s_N \end{matrix}\right)\left(\begin{matrix} \frac{A_{1,1}}{\sum_{k=1}^{N}A_{1,k}} & \cdots & \frac{A_{1,N}}{\sum_{k=1}^{N}A_{1,k}} \\ \vdots & \ddots & \vdots \\ \frac{A_{N,1}}{\sum_{k=1}^{N}A_{N,k}} & \cdots & \frac{A_{N,N}}{\sum_{k=1}^{N}A_{N,k}} \end{matrix}\right)=\left(\begin{matrix}s_1 & \cdots & s_i & \cdots & s_N \end{matrix}\right)[/latex]

この式を行列[latex]s,P[/latex]を使って[latex]sP=s[/latex]と同じだとみなすと、[latex]P[/latex]をマルコフ連鎖の推移確率行列としてみなせば、スコア[latex]s[/latex]はマルコフ連鎖の定常状態とみなせる。

ここで暫定的に[latex]\hat{s}(0)=\left(\begin{matrix} \frac{1}{N} & \cdots & \frac{1}{N} \end{matrix}\right)[/latex]として

[latex]\hat{s}(0)P=\hat{s}(1)[/latex]
[latex]\hat{s}(1)P=\hat{s}(2)[/latex]
[latex]\vdots[/latex]

とすれば

[latex]\lim_{x \to \infty}\hat{s}(x)=s[/latex]

と収束していく。

これがページランクアルゴリズムです。多分数式だらけで最初はわけわかんないと思いますが、

これ書くのに疲れたので今日は以上とさせていただきますw