ページランクへの誤解

もしも、私が、「グーグルは、極めて微小な値ではあるが、キャッチし、計算対象としている全てのウェブページにリンクの有無に拘わらず、数値を割り当てしている。そうでなければ、ページランクベクトルは、定まらない。」と言えば、その意味を日本では、何人の方が、ご存じなのでしょうか？。
（堅苦しく言えば、強連結＝既約→重複しない主固有値1→単一のページランクベクトルとなります。）それで、このようなタイトルとしました。

2006年頃には、日本語で書かれたページランクの本物の解説は、Google の秘密 - PageRank 徹底解説 の　「どうやって PageRank を求めるか」しかありませんでした。(注)

ところで、上記引用ページの計算は、学者の方ゆえ、机上の理論上は、全く完全なものですが、実際には、単なるべき乗法で、エクセルでも簡単に行えることをお見せしましょう。 （グーグルのページランクは、べき乗法で算出されています。ページランク特許の内容中に、数式にて明記されています。）

始めに、Google の秘密 - PageRank 徹底解説のリンク関係図を借用させて頂きます。

また、同ウェブページの「以下のような Octave スクリプトを適当なエディタで作成する。」の計算対象行列は、次のようなものです。

（なお、同ウェブサイトの著者も既に指摘されているように、規模が大きくなれば、理論上は、下記に引用したような行列では、単一のページランクベクトルを得ることは、絶対に不可能です。 固有値についてご参照）

	1	2	3	4	5	6	7
1		1	0.5		0.25	0.5
2	0.2		0.5	1/3
3	0.2			1/3	0.25
4	0.2				0.25
5	0.2			1/3		0.5	1
6					0.25
7	0.2
	1	1	1	1	1	1	1

上記のリンク関係から、著者の方は、まるで、線形代数のテキストにあるように

Google の秘密 - PageRank 徹底解説より引用

「ここでは横着をして GNU Octave という計算プログラムを使って固有値と固有ベクトルを実際に計算することとしよう。(略） 固有値は複素数も含めると7つあるが、このうち絶対値最大の固有値λは λ=1 である。これに対応する固有ベクトルは実ベクトルであり、（以下略）」

とし、主固有値→主固有ベクトルを算出し、これをもって、Ｇｏｏｇｌｅのページランク算出手法とされています。（教科書的に理解しやすいようにとの趣旨であると考えます。）

私は、エクセルで計算式の入力に数分しかかからない方法で、（パワー法で）同様の結果を得られることをお見せしましょう。

	初期 ベクトル	反復回数	反復回数	反復回数	反復回数	反復回数
	2	3	4	5	6	7
1	1		0.35	0.316667	0.282917	0.320972
2	0	0.2	0.166667	0.145	0.185556	0.155403
3	0	0.2	0.116667	0.153333	0.136806	0.140056
4	0	0.2	0.05	0.136667	0.09125	0.109639
5	0	0.2	0.266667	0.111667	0.212222	0.164292
6	0	0	0.05	0.066667	0.027917	0.053056
7	0	0.2	0	0.07	0.063333	0.056583
		1	1	1	1	1

反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数
8	9	10	11	12	13	14	15	16
0.293031	0.302019	0.303693	0.303734	0.303272	0.303674	0.303434	0.303546	0.303507
0.170769	0.166321	0.166367	0.165882	0.166299	0.166051	0.166166	0.166127	0.166133
0.141814	0.141098	0.140337	0.140652	0.140567	0.140563	0.140588	0.140567	0.140579
0.105267	0.106242	0.104924	0.105677	0.105341	0.105449	0.105438	0.105421	0.105439
0.183852	0.178079	0.179756	0.178377	0.179181	0.178812	0.178937	0.178919	0.178903
0.041073	0.044607	0.04452	0.044939	0.044594	0.044795	0.044703	0.044734	0.04473
0.064194	0.061635	0.060404	0.060739	0.060747	0.060654	0.060735	0.060687	0.060709
1	1	1	1	1	1	1	1	1

反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数	反復回数
17	18	19	20	21	22	23	24	25
0.303513	0.303517	0.303512	0.303516	0.303514	0.303515	0.303514	0.303514	0.303514
0.166137	0.166132	0.166136	0.166134	0.166134	0.166134	0.166134	0.166134	0.166134
0.140573	0.140575	0.140575	0.140575	0.140575	0.140575	0.140575	0.140575	0.140575
0.105427	0.105433	0.105431	0.105431	0.105431	0.105431	0.105431	0.105431	0.105431
0.178922	0.178909	0.178916	0.178913	0.178914	0.178914	0.178914	0.178914	0.178914
0.044726	0.04473	0.044727	0.044729	0.044728	0.044728	0.044728	0.044728	0.044728
0.060701	0.060703	0.060703	0.060702	0.060703	0.060703	0.060703	0.060703	0.060703
1	1	1	1	1	1	1	1	1

２４回目で、Google の秘密 - PageRank 徹底解説　と同様の数値を得ることができます。

0.303514

0.166134

0.140575

0.105431

0.178914

0.044728

0.060703

（注）
エクセルの場合、計算は、10^-16 で、打ち切りとなります。このため、計算精度は、10^-16とお考え下さい

なお、私は、エクセルで計算式を入力しましたが、（数分程度で終わります。）上記のようなパラメーター　ｄ　を考慮しない場合には、 Calculator for finite Markov chain 」というこのページで、 簡単に計算できます。下の表をコピペして、 Calculator for finite Markov chain に貼付け後、計算結果を表示してみて下さい。

下の表の数値は、Google の秘密 - PageRank 徹底解説と全く同一ですが、列ではなく、行の合計が1になっています。Calculator for finite Markov chain にて表示される計算結果が、小数点第四位四捨五入で、一致していることをお確かめください

0	0.2	0.2	0.2	0.2	0	0.2
1	0	0	0	0	0	0
0.5	0.5	0	0	0	0	0
0	0.33333	0.33333	0	0.33333	0	0
0.25	0	0.25	0.25	0	0.25	0
0.5	0	0	0	0.5	0	0
0	0	0	0	1	0	0