予約システム
背景色をお選びください
ページランク算出理論
現実のページランクについて
グーグルの順位決定方法
その他

(1)ページランクの計算方法の原理のもっとも分かりやすい例です。(実は、この例は、特許文書の例です。)

ウェブ世界が、次のようにたった3つのウェブページから構成されていると仮定します。

このリンク関係は、次のような簡単な数式で記述しえます。下記の式の左のX・Y・Zのそれぞれのウェブページについて、右側の式で他のページとの関係を示すと考えてください。

@X=Z  Xは、Zの発する唯一のリンクを受けています。

AY=X/2  Yは、Xの発する2つのリンクのうち、ひとつを受けています。

BZ=X/2+Y Zは、Xの発する2つのリンクのうちひとつを受け、かつ、Yの発する唯一のリンクを受けています

行列では、次のようにします。

リンクがされている場合には、1を入れる.

  X Y Z
X 0 0 1
Y 1 0 0
Z 1 1 0

列の合計を1にする。

  X Y Z
X 0 0 1
Y 0.5 0 0
Z 0.5 1 0

この行列を適当な初期ベクトル(=任意の数値の組み合わせのことです。この例では、1,0,0とします。)にかけて、反復計算して得られた数値(同じ数値の繰り返しになるまで)が、パラメーター d を考慮しない場合の(即ち1)ページランクの基礎数値です。

 なお、正確に言えば、リンク関係をグラフとみなし、隣接行列(リンクがある場合には、上記のように列に1を入れるのではなく行に1を入れることを意味します。)と考えるのが、根本発想ですが、このウェブサイトでは、上記形式で統一しています。(興味ある方は、英文ですが、Calculating Web Page Authority Using the PageRank Algorithm. を参照ください。私が知っている範囲では、もっともコンパクトにまとまっています。)

(線形代数をご存知の方用)

ページランクの算出が、上記のような手法で、算出されていることは、特許文書に示されている、下記の式から明白です。

∞=limAn0 (n→∞) なお、例えば、2 Ap1A20である旨、特許文書に明記されています。

0が、初期ベクトル(この例では、1,0,0)。Aは、英語でグーグル行列と呼ばれる下記の行列です。

A=(α/N ×1 )+(1−α)B この行列の詳細は、現実のページランク算出方法を見てください。1 は、太字にしていますがベクトルではなく、行列です。

変数の数が、少なければ、計算式の入力にそれほど時間は、かかりませんので、エクセルで簡単に計算できます。べき乗法又はパワー法=power methodと呼ばれる良く知られているごく簡単な計算方法です。

上の行列の例では、エクセルでは下記のように43回目の反復で、収束します。
エクセルでは数値表示上は10−30まで可能とされていますが、実際の計算は、10−16程度で打ち切りです。計算精度=10−16とお考えください。

  1回目 2回目 3回目 4回目 5回目 6回目 7回目 (略) (略) 41回目 42回目 43回目
X 1 0 0.5 0.5 0.25 0.5 0.375     0.400001 0.4 0.4
Y 0 0.5 0 0.25 0.25 0.125 0.25     0.2 0.2 0.2
Z 0 0.5 0.5 0.25 0.5 0.375 0.375     0.4 0.4 0.4

ウェブ上で、ページランクの数値計算原理を紹介されているウェブページがありますが、むしろ誤解を招くだけであると考えます。Google の秘密 - PageRank 徹底解説の数値計算例で検証しました。ページランクへの誤解ご参照。

なお、本物の数値計算例は、Calculating Web Page Authority Using the PageRank Algorithm. 9 Real-World Exampleにあり、約2700ページでの計算例です。

(2)8サイト間の例です。(ページランクの数値が、確率を示すものであることが、理解いただけるでしょう。)

次のようなリンク関係を想定します。(リンク関係図と表は、http://www.ams.org/featurecolumn/archive/pagerank.htmlから借用しています。)

スタート:@からスタートします。
1回目:ウェブサイト@は、A及びBにリンクしています。各0.5を配分
2回目:@のリンク先Aは、Cのみへリンクしています(0.5を配分)。また、@のリンク先Bは、AとDへリンクしています(各0.25配分)。
3回目:Aは、Cのみへリンクしています(0.25配分)、Cは、ADEへリンクしています。(Eは、0.25でADは、0.1666をそれぞれ配分
    
Dは、EFGへリンクしています。(Eのみ0.25、FGは、0.0833333を配分

以降は、順次、数値計算します。61回目で終わりました。なお、最終的に得られた数値をstationary distribution vectorと呼び、訳せば、定常分布ベクトルです。(=steady-state vector) 上記のようなパワー法による数値計算で、主固有ベクトル(=ページランク)へ収束することは、既に知られています。handbook of linear algebra(編集者:Kenneth H. Rosen) Adobe Reader 版682頁より)

なお、ページランクは、グーグル行列のL1ノルム(合計が1)の固有ベクトルそのものです。つまり、ページランクは、"ペロンベクトル"に他ならないというのが、英米の数学者の見解です。 詳細は、固有値についてをご参照下さい。

ウェブサイト スタート 1回目 2回目 3回目     61回目
@ 1 0 0 0     0.06
A 0 0.5 0.25 0.1666・・     0.0675
B 0 0.5 0 0     0.03
C 0 0 0.5 0.25     0.0675
D 0 0 0.25 0.1666・・・     0.0975
E 0 0 0 0.25     0.2025
F 0 0 0 0.0833     0.18
G 0 0 0 0.0833     0.295

これが、ページランクの計算方法の原理です。実際には、パラメーター d が加わります。現実のページランク算出方法をご参照。

論文の中で、ページランクの考案者は、「Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.」と明言し、計算対象の全てのウェブページのページランクの合計は、1になるとしていますが、これは、上記のような手法で算出されているからです。

@最後の数値(=ページランク)は、例えば、ある人が、サイト@(例えば、Google)からスタート(=検索)し、リンクをたどる場合に、最終的にどのサイトで終わるのかの可能性(確率)を意味することが、理解いただけるのではないでしょうか。(ランダムサーファーモデル参照)

A仮にサイト8に、10のウェブページがあった場合、上記の例では、0.295の数値が、ウェブサイト内の各ページへ再配分される形式で、各ウェブページのページランクが、決定されていると推測されます。計算式は、全く不明。(Google行列の数値計算対象は、あくまでも、外部とリンク関係にあるウェブページのみです。)

(注)内部リンクの扱いについては特許文書にて、A modification to avoid drawing unwarranted attention to pages with artificially inflated relevance is to ignore local links between documents and only consider links between separate domains. と明記され、数値計算上無視されます。

意訳:意図的に増加させた内部リンク(=関連)によって、ウェブページへ不当な関心を引き寄せることを防ぐ修正(方法)は、ウェブサイト内の内部リンクを無視し、別々のドメイン間のリンクのみを(ページランク計算対象として)考慮することである。

B上記の例では、理解しやすいように、1と0のみからなるベクトルから計算を初めていますが、初期ベクトルは、任意に選べますので、実際には、特許文書によれば、全てを1/Nにして、計算しているようです。

(注)
グーグルページランクの生の算出数値(浮動小数点数)は、当然、近似値にすぎません。容易に近似値を求めうるパワー法の長所ですが、同時に有効な近似値は、どのレベルかという問題が生じます。規模が、大きくなれば、ある方が主張するように「いつまでたっても計算が終わらない」というのは、当然であり、問題の核心は、どのレベルが有効な(意義を有する)近似値であるのかという点なのです。繰り返しになりますが、非常に数の多い(恐らく80億以上の)連立方程式を解いているのではなく、数値計算で近似値を求めているのです。
論文PDF版の図5をみると、10-8レベル程度になった時点で、反復計算を打ち切っています。なお、論文の図5の縦軸は、指数1目盛です。(特許文書では、100回程度の反復を行うとしています。)

一方、反復回数については、ダンピングファクター d の値が、大きく影響します。
@例えば、d=0.99の場合、意味のある近似値(10-8レベル)を得るには、約1800回の反復を要するに対し、d=0.85の場合、114回の反復で、有意義な近似値(10-8レベル)を得ることができるそうです。(Deeper inside pagerank  6.1Changing α より。理論面から検討しています。)
A一方、この論文(PDF版、執筆者は、同じスタンフォード大学の別人)では、実用的には、10回でも有効であると結論付けています。また、ページランク考案者も、特許文書その他で、反復をあまり多く行う必要はないと再三強調するとともに、計算対象行列の規模は、近似値を得るための反復回数には、全く影響がない旨を指摘し、グラフを掲げています。

以上をまとめると、google創設者両名が、d=0.85 (α=0.15)と設定したことは、有効近似値算出のためには、極めて有効な手法であったというのが、英米の学者の評価のようです。つまり、「収束は早い」と一般には考えられています。(0.85という設定値は、理論上、最後まで計算すれば収束に時間がかかるはずが、意義のある近似値を10-8レベルと仮定すれば、収束は早いという趣旨です。)
なお、α=0.15(d=0.85)とするリンク関係の修正がなければ、理論上、単一のページランクベクトルを算出しえません。現実のページランク算出方法ご参照。