前のページ 1/2 次のページ

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

名称の由来は、ウェブページの"ページ"と、グーグルの創設者の一人ラリー・ペイジ (Larry Page) のファミリーネームをかけたものである。

PageRank™はグーグルの商標であり、またPageRankの処理は特許が取得されている()。しかしながら、特許はスタンフォード大学に帰属しており、グーグルではない。グーグルはスタンフォード大学から同特許の権利を独占的にライセンスされている。同大学は特許の使用権と交換にグーグルから180万株を譲渡されている; 株式は2005年に3億3600万ドルで売却された。

◆ 概要

◇ 発想

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

# 学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。

# また、被引用数を用いる考え方以外にも、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。

# また、乱発されたリンクはあまり価値がないと考えられる。リンク集のようなとにかくたくさんリンクすることを目的としている場合、リンク先のウェブページに強く注目しているとは言い難い。

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

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

◇ 方法

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

# 各ページは、固有の得点を持っている。
各リンクもまた、固有の得点を持っている。

# あるページ X に対して、

#* X の得点を P とする。

#* 他のページから X に対して張られているリンクの得点をそれぞれ $I\_1,\; ...,\; I\_n$ とする。

#* X から他のページに張られているリンクの得点をそれぞれ $O\_1,\; ...,\; O\_m$ とする。

# このとき、次が成り立つものとする。

: $I\_1\; +\; ...\; +\; I\_n\; =\; P$

:

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

この得点が高いほど、そのページは重要であると考えられる。

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

◇ グラフ理論

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

# WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。

# このとき、このグラフの隣接行列を転倒したものを A =(a_ij) とし、
行列 B = (b_ij) を 次によって定義する。

# B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。

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

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

◇ 別の定義式

ファイル形式の論文がウェブ上にて公表されている。[外部リンク] 参照(英語)[外部リンク] 日本語による平易な解説

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

・ $PR\backslash left(T\_n\backslash right)$:ページAにリンクしているページ$T\_n$のページランク。仮にページAに対して3つのページがリンクしているとした場合、$T\_1$から$T\_3$までの各ページを表す。

・ $C\backslash left(T\_n\backslash right)$:ページ$T\_n$に含まれる他ページ(Aでも$T\_n$でもないページ)へのリンクの総数。(注:『他ページ』に内部リンクが含まれるのか否かについてはstub)

・ d:ダンピング・ファクター。通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。(常に$d\backslash le1$)

◆ Google ツールバー

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

◆ rel="nofollow"

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

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

Buzzurl、del.icio.usといったソーシャルブックマークにおいても、ブックマークスパム対策として、この属性が使われる傾向にある。一方、はてなブックマークは、この属性を持たせていないため、ページランクを上げる目的としてのブックマーク登録が後を絶たない。

◆ 脚注

◆ 外部リンク

・ [外部リンク] Google の秘密 - PageRank 徹底解説

・ [外部リンク] ページランク特許(Google patent, 英文,ページランク算出手法が明記されている。)

・ [外部リンク] The Anatomy of a Large-Scale Hypertextual Web Search Engine(ページランクに関するGoole創設者の論文,定義式については、2.1.1 Description of PageRank Calculation参照。)

・ [外部リンク] The Pagerank Citation Ranking:Bringing order to the web(ページランクに関するGoole創設者の論文?)

・ [外部リンク] How Google Finds Your Needle in the Web's Haystack (数学者による最も平易かつ信頼性の高いページランクの解説。英文)

前のページ 1/2 次のページ

・ページランク page1

・ページランク page2