ページランク

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ページランクの動作概念図

ページランク (PageRank) は、ウェブページの重要度を決定するためのアルゴリズムであり、検索エンジンGoogleにおいて、検索語に対する適切な結果を得るために用いられている中心的な技術。名称の由来は、ウェブページの"ページ"と、Googleの創設者の一人、ラリー・ペイジをかけたものである。

PageRank™ はGoogleの商標であり、また PageRank の処理は特許が取得されている(アメリカ合衆国特許第6,285,999号)。ただし、特許はGoogleではなくスタンフォード大学に帰属しており、Googleはスタンフォード大学から同特許の権利を独占的にライセンスされている。なお、同大学は特許の使用権と交換にGoogleから180万株を譲渡されているが、その株式は2005年に3億3,600万ドルで売却された。[1] [2]

概要[編集]

発想[編集]

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

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

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

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

方法[編集]

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

  1. 各ページは、固有の得点を持っている。
    各リンクもまた、固有の得点を持っている。
  2. あるページ X に対して、
    • X の得点を P とする。
    • 他のページから X に対して張られているリンクの得点をそれぞれ I_1, ..., I_n とする。
    • X から他のページに張られているリンクの得点をそれぞれ O_1, ..., O_m とする。
  3. このとき、次が成り立つものとする。
I_1 + ... + I_n = 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 は推移確率行列と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。

別の定義式[編集]

ファイル形式の論文がウェブ上にて公表されている。参照(英語)

上記の論文によれば、あるページ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社が配布しているGoogle ツールバーを用いれば、このアルゴリズムによる各ページの評価点を0〜10の11段階で表示することができる。ただしこの評価点については、幾分古いデータが用いられる(年に3回程度更新)などで、必ずしもその時々の実態を反映したものではないため、飾りとしての意味しか持たないとの見方もある。近年は有料でリンクを販売しているサイトの評価点が下落傾向にある。

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から受け取る(便宜的表現)ページランクは無となる。

なお、Wikipediaを含むMediaWikiの外部リンクにはすべてこの属性を持たせている。これは、Wikipedia(MediaWiki)が宣伝の道具に利用されるのを防ぐためである。

Buzzurl、del.icio.usといったソーシャルブックマークにおいても、ブックマークスパム対策として、この属性が使われる傾向にある。

脚注[編集]

[ヘルプ]
  1. ^ Lisa M. Krieger (2005年12月1日). “Stanford Earns $336 Million Off Google Stock”. San Jose Mercury News, cited by redOrbit. 2009年2月25日閲覧。
  2. ^ Richard Brandt. “Starting Up. How Google got its groove”. Stanford magazine. 2009年2月25日閲覧。

関連項目[編集]

  • 検索エンジン最適化 - SEO。対象ページのページランクを上げるために行われるサイト構成などの最適化

外部リンク[編集]