マイムの部屋

社内SEが,興味をもったことを書いていきます.

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

参考資料

  • Amy, N.L. and Carl,D.M.:Google's Pagerank and Beyond: The Science of Search Engine Rankings(2006).岩野和生,黒川利明,黒川 洋 (訳)Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて(2009).