弊社プロダクトへの利用を考えてページランクアルゴリズムを実装しました。
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]と収束していく。
これがページランクアルゴリズムです。多分数式だらけで最初はわけわかんないと思いますが、
これ書くのに疲れたので今日は以上とさせていただきますｗ
