ページランク

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ページランクは、World Wide Web上の文書や画像を検索する検索エンジンの一つであるグーグルが採用している、ウェブページの重要性を測るアルゴリズム。グーグル社の商標(PageRank™)でもある。

名称の由来は、ウェブページの"ページ"ではなく、グーグルの創設者の一人ラリー・ページ(Lary Page)氏のファミリーネームにある。

[編集] 概要

[編集] 発想

PageRankアルゴリズムの発想は、引用に基づく学術論文の評価に似ている。

学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。
また、被引用数を用いる考え方以外にも、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。
また、乱発されたリンクはあまり価値がないと考えられる。リンク集のようなとにかくたくさんリンクすることを目的としている場合、リンク先のウェブページに強く注目しているとは言い難い。

この発想を、数億～数十億ページにのぼるウェブページのリンク関係にも適用したのがPageRankである。（PageRankの登場まで、このような大規模なリンク関係に適用するのは難しかった。）

この方法を適用することにより、仲間内でリンクし合っているだけのサイトの重要度が上がりにくくなり、リンク集のような多くのリンクを張っているだけのサイトからのリンクの重要性を相対的に減らす効果がある。

[編集] 方法

以上を少し単純化して数学的に表すと、次のような方法が考えられる。

各ページは、固有の得点を持っている。
各リンクもまた、固有の得点を持っている。
あるページ X に対して、
- X の得点を P とする。
- 他のページから X に対して張られているリンクの得点をそれぞれ $I 1,..., I n$ とする。
- X から他のページに張られているリンクの得点をそれぞれ $O 1,..., O m$ とする。
このとき、次が成り立つものとする。

I 1 + ... + I n = P

$O_1 = ... = O_m = \frac{P}{m} \left( = \frac{\sum_{i=1}^n I_i}{m} \right)$

すなわち、各ページに「流れ込む」リンクの得点の総和と、各ページから「流れ出す」リンクの得点の総和が等しくなるようにして、その総和をそのページの得点と考えるのである。この得点が高いほど、そのページは重要であると考えられる。

全体に亘って矛盾が生じないようにうまく得点を割り振る必要があるが、これは一種のフローの問題であり、この問題の解法については様々な理論が考え出されている。

[編集] グラフ理論

グラフ理論の言葉を使うなら、次のようなことである。

WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。
このとき、このグラフの隣接行列を転倒したものを A =(a_ij) とし、
行列 B = (b_ij) を次によって定義する。
$b_{ij} = \frac{a_{ij}}{\sum_{k} a_{kj}}$
B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。

補足すると、上の定義に於いて、B は A の各要素をその列の非零要素の数で割ったものである。従って、B の各列の和は 1 になっている。

B は推移確率行列と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。

[編集] 別の定義式

ファイル形式の論文がウェブ上にて公表されている。参照（英語）日本語による平易な解説

上記の論文によれば、あるページAのページランクPR(A)は、次のような式で定義される。

$PR\left(A\right) = \left(1-d \right) + d\sum_{i=1}^n \frac{PR\left(T_i \right)}{C\left(T_i \right)}$

$\Longleftrightarrow PR\left(A\right) = 1-d + d\left(\frac{PR\left(T_1 \right)}{C\left(T_1 \right)} + ... + \frac{PR\left(T_n \right)}{C\left(T_n \right)} \right)$

$PR\left(T_n\right)$ ：ページAにリンクしているページ $T n$ のページランク。仮にページAに対して3つのページがリンクしているとした場合、 $T 1$ から $T 3$ までの各ページを表す。
$C\left(T_n\right)$ ：ページ $T n$ に含まれる他ページ（Aでも $T n$ でもないページ）へのリンクの総数。（注：『他ページ』に内部リンクが含まれるのか否かについてはstub）
d：ダンピング・ファクター。通常0.85に設定されるが、恣意的にページランクを上げようとする者に対しては、より小さい値に設定される。（常に $d\le1$ ）

[編集] Google ツールバー

グーグル社が配布しているGoogle ツールバーを用いれば、このアルゴリズムによる各ページの評価点を10段階で表示することができる。ただしこの評価点については、幾分古いデータが用いられるなどで、必ずしもその時々の実態を反映したものではないため、飾りとしての意味しか持たないとの見方もある。

[編集] rel="nofollow"

リンクに属性 rel="nofollow" を加えることで、同リンクをページランクの計算対象から除外することが可能となっている。これは、ブログにおけるコメントスパムへの対策などを主目的として、2005年のはじめにGoogleにより提案されたものである。例えばページAからページBにリンクする場合、ページBのURLを仮にhttp://ja.wikipedia.org/とするならば、<a href="http://ja.wikipedia.org/" rel="nofollow"></a>とすることで、ページBがページAから受け取る（便宜的表現）ページランクは無となる。

[編集] 外部リンク

"http://ja.wikipedia.org../../../%E3%83%9A/%E3%83%BC/%E3%82%B8/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%A9%E3%83%B3%E3%82%AF.html" より作成

カテゴリ: アルゴリズム | グラフ理論 | 検索エンジン