08/06/01 15:05:36 4ZiwWtc20
自分の求めている動画を見つける方法
それは、自分の求めているサイトを見つける方法に似ているのかもしれない。
URLﾘﾝｸ(ja.wikipedia.org)
ページランク（PageRank）は、World Wide Web上の文書や画像を検索する検索エンジンの一つであるグーグルが採用している、ウェブページの重要性を測るアルゴリズムである。グーグル社の商標(PageRank?)である。
PageRankアルゴリズムの発想は、引用に基づく学術論文の評価に似ている。
1. 学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。
2. また、被引用数を用いる考え方以外にも、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。
3. また、乱発されたリンクはあまり価値がないと考えられる。リンク集のようなとにかくたくさんリンクすることを目的としている場合、リンク先のウェブページに強く注目しているとは言い難い。
この発想を、数億～数十億ページにのぼるウェブページのリンク関係にも適用したのがPageRankである。（PageRankの登場まで、このような大規模なリンク関係に適用するのは難しかった。）
この方法を適用することにより、仲間内でリンクし合っているだけのサイトの重要度が上がりにくくなり、リンク集のような多くのリンクを張っているだけのサイトからのリンクの重要性を相対的に減らす効果がある。
[編集] 方法
以上を少し単純化して数学的に表すと、次のような方法が考えられる。
1. 各ページは、固有の得点を持っている。
各リンクもまた、固有の得点を持っている。
2. あるページ X に対して、
* X の得点を P とする。
* 他のページから X に対して張られているリンクの得点をそれぞれ I1,...,In とする。
* X から他のページに張られているリンクの得点をそれぞれ O1,...,Om とする。
3. このとき、次が成り立つものとする。
I1 + ... + In = P
O_1 = ... = O_m = \frac{P}{m} \left( = \frac{\sum_{i=1}^n I_i}{m} \right)
すなわち、各ページに「流れ込む」リンクの得点の総和と、各ページから「流れ出す」リンクの得点の総和が等しくなるようにして、その総和をそのページの得点と考えるのである。 この得点が高いほど、そのページは重要であると考えられる。
全体に亘って矛盾が生じないようにうまく得点を割り振る必要があるが、これは一種のフローの問題であり、この問題の解法については様々な理論が考え出されている。
[編集] グラフ理論
グラフ理論の言葉を使うなら、次のようなことである。
1. WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。
2. このとき、このグラフの隣接行列を転倒したものを A =(aij) とし、
行列 B = (bij) を 次によって定義する。
b_{ij} = \frac{a_{ij}}{\sum_{k} a_{kj}}
3. B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。
補足すると、上の定義に於いて、B は A の各要素をその列の非零要素の数で割ったものである。 従って、B の各列の和は 1 になっている。
B は推移確率行列と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。