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

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

PageRank アルゴリズムの発想は、引用に基づく学術論文の評価に似ている。
学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。

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

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

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

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

以上を少し単純化して数学的に表すと、次のような方法が考えられる。
各ページは、固有の得点を持っている。
各リンクもまた、固有の得点を持っている。

あるページ X に対して、

X の得点を P とする。

他のページから X に対して張られているリンクの得点をそれぞれ I 1 , … , I n {\displaystyle I_{1},\dotsc ,I_{n}} とする。

X から他のページに張られているリンクの得点をそれぞれ O 1 , … , O m {\displaystyle O_{1},\dotsc ,O_{m}} とする。


このとき、次が成り立つものとする。
I 1 + ⋯ + I n = P {\displaystyle I_{1}+\dotsb +I_{n}=P} O 1 = ⋯ = O m = P m ( = ∑ i = 1 n I i m ) {\displaystyle O_{1}=\dotsb =O_{m}={\frac {P}{m}}\left(={\frac {\sum _{i=1}^{n}I_{i}}{m}}\right)}

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

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

グラフ理論の言葉を使うなら、次のようなことである。
WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。

この有向グラフの隣接行列を転置したものを A =(aij) とし、行列 B = (bij) を b i j = a i j / ∑ k a k j {\displaystyle b_{ij}=a_{ij}{\bigg /}\textstyle \sum _{k}a_{kj}} で定義する。