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

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

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

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

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

サイトが\(N\)個あるとする。

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

サイト\(i\)の得点\(s_i\)を求めたい。

導出

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

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

つまりサイト\(i\)はサイト\(j\)に対して

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

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

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

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

スコアを与えるではなくスコアを与えてもらう、という立場に逆転して考えると、自分のスコアは与えてもらったスコアの総和である。だから
\(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\)

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

\(s_i = \sum_{j=1}^{N}\frac{A_{j,i}}{\sum_{k=1}^{N}A_{j,k}}s_j\)

こうなる。

これを行列で表すと

\(\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)\)

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

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

\(\hat{s}(0)P=\hat{s}(1)\)
\(\hat{s}(1)P=\hat{s}(2)\)
\(\vdots\)

とすれば

\(\lim_{x \to \infty}\hat{s}(x)=s\)

と収束していく。

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

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