ページランク

ファイル:Linkstruct2.svg

ページランクの動作概念図

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

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

概要[]

発想[]

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

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

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

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

方法[]

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

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

I 1 + . . . + I n = P {\displaystyle I_{1}+...+I_{n}=P} {\displaystyle I_{1}+...+I_{n}=P} O 1 = . . . = O m = P m ( = ∑ i = 1 n I i m ) {\displaystyle 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 i j = a i j ∑ k a k j {\displaystyle b_{ij}={\frac {a_{ij}}{\sum _{k}a_{kj}}}} {\displaystyle b_{ij}={\frac {a_{ij}}{\sum _{k}a_{kj}}}}
3. B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。

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

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

別の定義式[]

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

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

P R ( A ) = ( 1 − d ) + d ∑ i = 1 n P R ( T i ) C ( T i ) {\displaystyle PR\left(A\right)=\left(1-d\right)+d\sum _{i=1}^{n}{\frac {PR\left(T_{i}\right)}{C\left(T_{i}\right)}}}

⟺ P R ( A ) = 1 − d + d ( P R ( T 1 ) C ( T 1 ) + . . . + P R ( T n ) C ( T n ) ) {\displaystyle \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)} {\displaystyle \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)}

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

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

外部リンク[]

• PageRank Lookup
• Google の秘密 - PageRank 徹底解説
• Increase PR Increase your Google PageRank
• TOMATOES GROWING TOMATOES GROWING

テンプレート:Google Inc.

ar:ترتيب الصفحةcs:PageRankeu:PageRankhe:PageRankhu:PageRankit:PageRankkk:PageRankko:페이지랭크sk:PageRanksv:PageRankth:เพจแรงก์

このページの内容は、ウィキペディアから取られています。オリジナルの記事は、ページランクにあります。この記事の著作権者のリストは、ページの履歴を御覧ください。The Unofficial Google Wiki 日本語版と同じく、ウィキペディアのテキストは、GNU Free Documentation Licenseで提供されています。

特に記載のない限り、コミュニティのコンテンツはCC BY-SAライセンスの下で利用可能です。