ページランクのソースを表示

'''ページランク''' (PageRank) は、[[ウェブページ]]の重要度を決定するための[[アルゴリズム]]であり、[[検索エンジン]]の[[Google 検索|Google]]において、検索語に対する適切な結果を得るために用いられている中心的な技術。Googleの創設者のうち[[ラリー・ペイジ]]と[[セルゲイ・ブリン]]によって[[1998年]]に発明された{{sfn|Langville|Meyer|2011|loc=Glossary - PageRank}}{{sfn|Brin|Page|1998}}。名称の由来は、ウェブページの"ページ"とラリー・ペイジの[[姓]]をかけたものである。

PageRankはGoogleの[[商標]]であり、またPageRankの処理は[[特許]]が取得されている<ref>{{US patent|6285999}}</ref>。ただし、特許はGoogleではなく[[スタンフォード大学]]に帰属しており、Googleはスタンフォード大学から同特許の権利を独占的にライセンスされている。なお、同大学は特許の使用権と交換にGoogleから180万株を譲渡されているが、その株式は2005年に3億3,600万ドルで売却された<ref>
{{cite web
|url=http://www.redorbit.com/news/education/318480/stanford_earns_336_million_off_google_stock/
|title=Stanford Earns $336 Million Off Google Stock
|author=Lisa M. Krieger
|publisher=San Jose Mercury News, cited by redOrbit
|date=1 December 2005
|accessdate=2009-02-25}}
</ref><ref>
{{cite web
|url=http://www.stanfordalumni.org/news/magazine/2004/novdec/features/startingup.html
|title=Starting Up. How Google got its groove
|author=Richard Brandt
|accessdate=2009-02-25
|publisher=Stanford magazine}}
</ref>。

== 概要 ==
=== 発想 ===
[[File:PageRank-hi-res.png|thumb|250px|PageRankの動作概念図]]
PageRank アルゴリズムの発想は、[[引用]]に基づく[[学術論文]]の評価に似ている。

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

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

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

=== 方法 ===
以上を少し単純化して[[数学]]的に表すと、次のような方法が考えられる。
# 各ページは、固有の得点を持っている。<br/>各リンクもまた、固有の得点を持っている。
# あるページ X に対して、
#* X の得点を P とする。
#* 他のページから X に対して張られているリンクの得点をそれぞれ <math>I_1, \dotsc, I_n</math> とする。
#* X から他のページに張られているリンクの得点をそれぞれ <math>O_1, \dotsc, O_m</math> とする。
# このとき、次が成り立つものとする。
: <math>I_1 + \dotsb + I_n = P</math>
: <math>O_1 = \dotsb = O_m = \frac{P}{m} \left( = \frac{\sum_{i=1}^n I_i}{m} \right)</math>

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

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

=== グラフ理論 ===
[[グラフ理論]]の言葉を使うなら、次のようなことである。
# WWW上の各ページをノードと見なし、リンクをエッジと見なした[[有向グラフ]]を考える。
# この有向グラフの[[隣接行列]]を<math>A=(a_{ij})</math>とし、[[行列 (数学)|行列]]<math> B=(b_{ij})</math> を <math> b_{ij} = a_{ji} \bigg/ \textstyle\sum_{k} a_{jk}</math> で定義する。
# 行列<math>(1-d)J_N/N+dB</math>の最大[[固有値]]に属する[[固有ベクトル]]を求める。ここで<math>J_N</math>は要素が全て1の<math>N\times N</math>行列である。固有ベクトルの各要素の値が、求めるべき各ページの得点である。

補足すると、上の定義において、<math>B</math> は<math>A</math>の[[転置行列]] <math>A^T</math>の各要素をその列の非零要素の数で割ったものである。 従って、<math>B</math> の各列の和は 1 になっている。

<math>B</math> は'''[[マルコフ連鎖|推移確率行列]]'''と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。

=== 別の定義式 ===
{{harvtxt|Brin|Page|1998}}によれば、あるページAのページランクPR(A)は、次の式で定義される{{sfn|Brin|Page|1998|loc=2.2.1 Description of PageRank Calculation}}。
:<math>PR\left(A\right) = \frac{1-d}{N} + d\sum_{i=1}^n \frac{PR\left(T_i \right)}{C\left(T_i \right)}</math>
* <math>PR\left(T_n\right)</math>：ページAにリンクしているページ<math>T_n</math>のページランク。仮にページAに対して3つのページがリンクしているとした場合、<math>T_1</math>から<math>T_3</math>までの各ページを表す。
* <math>C\left(T_n\right)</math>：ページ<math>T_n</math>に含まれる他ページへのリンクの総数。
* <math>d</math>：ダンピング・ファクター。通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。（常に<math>0 \le d \le 1</math>）

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*{{citation
|last1      = Brin
|first1     = S. 
|author1-link = セルゲイ・ブリン
|last2      = Page
|first2     = L. 
|author2-link = ラリー・ペイジ
|year       = 1998
|title      = The Anatomy of a Large-Scale Hypertextual Web Search Engine
|url        = http://ilpubs.stanford.edu:8090/361/
|ref        = harv
}}
*{{cite book
|last1      = Langville
|first1     = Amy N.
|last2      = Meyer
|first2     = Carl D.
|year       = 2011
|origyear   = 2006
|title      = Google's PageRank and Beyond
|url        = {{google books|KsHTl_2Pfl8C|plainurl=yes}}
|publisher  = Princeton University Press
|isbn       = 140083032X
|ref        = harv
}}
** [[邦訳]] {{cite book
|和書
|last1      = Langville
|first1     = Amy N.
|last2      = Meyer
|first2     = Carl D.
|translator = 岩野和生, 黒川利明, 黒川洋
|year       = 2009
|title      = Google PageRankの数理
|isbn       = 9784320122390
|publisher  = 共立出版
}}
*{{citation
|last1      = Page
|first1     = L. 
|author1-link = ラリー・ペイジ
|last2      = Brin
|first2     = S. 
|author2-link = セルゲイ・ブリン
|last3      = Motwani
|first3     = Rajeev
|last4      = Winograd
|first4     = Terry 
|author4-link = テリー・ウィノグラード
|year       = 1999
|title      = The PageRank Citation Ranking: Bringing Order to the Web
|url        = http://ilpubs.stanford.edu:8090/422/
|ref        = harv
}}

== 関連項目 ==
* [[検索エンジン最適化]] - SEO。対象ページのページランクを上げるために行われるサイト構成などの最適化

== 外部リンク ==
* [http://www.ams.org/featurecolumn/archive/pagerank.html How Google Finds Your Needle in the Web's Haystack (数学者による最も平易かつ信頼性の高いページランクの解説。英文)]
{{デフォルトソート:へえしらんく}}
[[Category:アルゴリズム]]
[[Category:グラフ理論]]
[[Category:検索エンジン]]
[[Category:Google]]
[[Category:クラウドソーシング]]
[[Category:エポニム]]