ページランク
PageRank アルゴリズムの発想は、引用に基づく学術論文の評価に似ている。
学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。
さらに、被引用数を用いる考え方に加えて、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。
ただし、乱発されたリンクにはあまり価値がないと考えられる。リンク集のように、とにかくたくさんリンクすることを目的としている場合には、リンク先のウェブページに強く注目しているとは言い難い。
この発想を、数億~数十億ページにのぼるウェブページのリンク関係にも適用したのが PageRank である(PageRank の登場まで、このような大規模なリンク関係に適用するのは難しかった)。
この方法を適用することにより、仲間内でリンクし合っているだけのサイトの重要度が上がりにくくなり、リンク集のような多くのリンクを張っているだけのサイトからのリンクの重要性を相対的に減らす効果がある。
グラフ理論の言葉を使うなら、次のようなことである。
WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。
この有向グラフの隣接行列を転置したものを A =(aij) とし、行列 B = (bij) を b i j = a i j / ∑ k a k j {\displaystyle b_{ij}=a_{ij}{\bigg /}\textstyle \sum _{k}a_{kj}} で定義する。
B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。
補足すると、上の定義において、B は A の各要素をその列の非零要素の数で割ったものである。 従って、B の各列の和は 1 になっている。
B は推移確率行列と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。