PageRank
PageRankに関しての知識を手に入れるために以下の本を参考にした.ページ\(P_i\)のPageRankは,\(r(P_i)\)と書く.そして,\(P_i\)を指しているすべてのページのPageRankの総和となる.
\[
r(P_i)=\sum_{P_j \in B_{P_{i}}} \frac{r(P_j)}{|P_j|}
\]
\(B_{P_{i}}\)は,\(P_i\)を指すページの集合であり,\(|P_j|\)は,ページ\(P_j\)からの出リンクの個数である.
例: \[ \left( \begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{array} \right) \]
例: \[ \left( \begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{array} \right) \]
- \(r(P_1)\)=\(\frac{1}{3}r(P_3)\)
- \(r(P_2)\)=\(\frac{1}{2}r(P_1)+\frac{1}{3}r(P_3)\)
- \(r(P_3)\)=\(\frac{1}{2}r(P_1)\)
- \(r(P_4)\)=\(\frac{1}{2}r(P_5)+\frac{1}{2}r(P_6)\)
- \(r(P_5)\)=\(\frac{1}{3}r(P_3)+\frac{1}{2}r(P_4)\)
- \(r(P_6)\)=\(\frac{1}{2}r(P_4)+\frac{1}{2}r(P_5)\)
初期値 | 1巡目 | 2巡目 | 3巡目 | PageRank | |
\(r(P_1)\) | 1 | \(\frac{1}{3}\) | \(\frac{1}{6}\) | \(\frac{1}{18}\) | 6 |
\(r(P_2)\) | 1 | \(\frac{5}{6}\) | \(\frac{1}{3}\) | \(\frac{5}{36}\) | 4 |
\(r(P_3)\) | 1 | \(\frac{1}{2}\) | \(\frac{1}{6}\) | \(\frac{1}{12}\) | 5 |
\(r(P_4)\) | 1 | 1 | \(\frac{11}{12}\) | \(\frac{19}{24}\) | 1 |
\(r(P_5)\) | 1 | \(\frac{5}{6}\) | \(\frac{2}{3}\) | \(\frac{37}{72}\) | 3 |
\(r(P_6)\) | 1 | 1 | \(\frac{11}{12}\) | \(\frac{19}{24}\) | 1 |