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