ページランク

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

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

概要

発想

PageRankの動作概念図

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

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

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

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

方法

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

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

${\displaystyle I_{1}+\dotsb +I_{n}=P}$

${\displaystyle O_{1}=\dotsb =O_{m}={\frac {P}{m}}\left(={\frac {\sum _{i=1}^{n}I_{i}}{m}}\right)}$

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

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

グラフ理論

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

1. WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。
2. この有向グラフの隣接行列を${\displaystyle A=(a_{ij})}$とし、行列${\displaystyle B=(b_{ij})}$ を ${\displaystyle b_{ij}=a_{ji}{\bigg /}\textstyle \sum _{k}a_{jk}}$ で定義する。
3. 行列${\displaystyle (1-d)J_{N}/N+dB}$の最大固有値に属する固有ベクトルを求める。ここで${\displaystyle J_{N}}$は要素が全て1の${\displaystyle N\times N}$行列である。固有ベクトルの各要素の値が、求めるべき各ページの得点である。

補足すると、上の定義において、${\displaystyle B}$ は${\displaystyle A}$の転置行列 ${\displaystyle A^{T}}$の各要素をその列の非零要素の数で割ったものである。 従って、${\displaystyle B}$ の各列の和は 1 になっている。

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

別の定義式

Brin & Page (1998)によれば、あるページAのページランクPR(A)は、次の式で定義される^[6]。

${\displaystyle PR\left(A\right)={\frac {1-d}{N}}+d\sum _{i=1}^{n}{\frac {PR\left(T_{i}\right)}{C\left(T_{i}\right)}}}$

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

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. Langville & Meyer 2011, Glossary - PageRank.
2. Brin & Page 1998.
3. アメリカ合衆国特許第 6,285,999号
4. Lisa M. Krieger (1 December 2005). “Stanford Earns $336 Million Off Google Stock”. San Jose Mercury News, cited by redOrbit. 2009年2月25日閲覧。
5. Richard Brandt. “Starting Up. How Google got its groove”. Stanford magazine. 2009年2月25日閲覧。
6. Brin & Page 1998, 2.2.1 Description of PageRank Calculation.

参考文献

• Brin, S.; Page, L. (1998), The Anatomy of a Large-Scale Hypertextual Web Search Engine, http://ilpubs.stanford.edu:8090/361/ 
• Langville, Amy N.; Meyer, Carl D. (2011) [2006]. Google's PageRank and Beyond. Princeton University Press. ISBN 140083032X. https://books.google.co.jp/books?id=KsHTl_2Pfl8C 
  • 邦訳 Langville, Amy N.、Meyer, Carl D. 著、岩野和生, 黒川利明, 黒川洋 訳『Google PageRankの数理』共立出版、2009年。ISBN 9784320122390。 
• Page, L.; Brin, S.; Motwani, Rajeev; Winograd, Terry (1999), The PageRank Citation Ranking: Bringing Order to the Web, http://ilpubs.stanford.edu:8090/422/ 

関連項目

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

外部リンク

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