PageRank 的計算，就是求屬于這個推移概率行列最大特性值的固有矢量(優(yōu)固有矢量)。
這是因為，當線性變換系 t→∞ 漸近時，我們能夠根據(jù)變換行列的"絕對價值最大的特性值"和"屬于它的固有矢量"將其從根本上記述下來。換句話說，用推移概率行列表示的概率過程，是反復對這個行列進行乘法運算的一個過程，并且能夠計算出前方狀態(tài)的概率。
再者，雖然聽起來很難,但是求特性值和固有矢量的值是能夠嚴密分析的一種基礎(chǔ)的數(shù)學手段。我們能夠自由地給矢量的初始值賦值，但是因為不斷地將行列相乘，得到的矢量卻會集中在一些特定數(shù)值的組合中。我們把那些穩(wěn)定的數(shù)值的組合稱為固有矢量，把固有矢量中特征性的標量(scalar)稱為特性值，把這樣的計算方法總稱為分解特性值，把解特性值的問題稱為特性值問題。
(*注) 對 N 次的正方行列 A 把滿足 Ax =λx 的數(shù) λ 稱為 A 的特性值，稱 x 為屬于 λ 的固有矢量。如果你怎么也不能適應行列的概念的話，你也可以考慮 N×N 的二元排列就可以了。同時，也可以把矢量考慮成為長度為 N 的普通的(一元)排列就可以了。
簡單的例子
讓我們用簡單的例子來試著逐次計算 PageRank 。首先考慮一下有像下圖表示那樣的鏈接關(guān)系的7個HTML文件。并且，這些HTML文件間的鏈接關(guān)系只是閉合于這1-7的文件中。也就是說，除了這些文檔以外沒有其他任何鏈接的出入。另外請注意，所有的頁面都有正向和反向鏈接(即沒有終點)，這也是后面將提出的一個重要假定,在此暫且不深入探討。
 |
| 表示頁面間互相鏈接關(guān)系的推移圖 |
首先，把這張推移圖圖表構(gòu)造的鄰接列表表示為排列式，就有以下式子。即，根據(jù)各個鏈接源ID列舉鏈接目標的ID。
鏈接源I D 鏈接目標 ID
1 2,3 ,4,5, 7
2 1
3 1,2
4 2,3,5
5 1,3,4,6
6 1,5
7 5
以這個鄰接列表中所表示的鏈接關(guān)系的鄰接行列 A 是以下這樣的 7×7 的正方行列。一個僅有要素 0 和 1 位圖行列(bitmap matrix)。橫向查看第 i 行表示從文件 i 正向鏈接的文件ID。
A = [
0, 1, 1, 1, 1, 0, 1;
1, 0, 0, 0, 0, 0, 0;
1, 1, 0, 0, 0, 0, 0;
0, 1, 1, 0, 1, 0, 0;
1, 0, 1, 1, 0, 1, 0;
1, 0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 1, 0, 0;
]
PageRank 式的推移概率行列 M ，是將 A 倒置后將各個數(shù)值除以各自的非零要素后得到的。即以下這個 7×7 的正方行列。橫向查看第 i 行非零要素表示有指向文件 i 鏈接的文件ID(文件 i 的反向鏈接源)。請注意，各縱列的值相加的和為 1(全概率)。
M = [
0, 1, 1/2, 0, 1/4, 1/2, 0;
1/5, 0, 1/2, 1/3, 0, 0, 0;
1/5, 0, 0, 1/3, 1/4, 0, 0;
1/5, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 1/3, 0, 1/2, 1;
0, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 0, 0, 0, 0;
]
表示 PageRank 的矢量 R (各個的頁面的等級數(shù)的隊列)，存在著 R = cMR 的關(guān)系(c 為定量)。在這種情況下，R 相當于線形代數(shù)中的固有矢量，c 相當于對應特性值的倒數(shù)。為了求得 R ，只要對這個正方行列 M 作特性值分解就可以了。
在分解特性值時有相應的各種各樣的數(shù)值分析法,但是本文將不在這里對各種方法詳細說明，請讀者自己去閱讀一本恰當?shù)慕炭茣?在你的暑假里一定有這么一本被埋沒的教科書)。在此，我們就暫且使用決 GNU Octave 這個計算程序?qū)嶋H計算一下特性值和固有矢量。
(*注) GNU Octave ，是支持數(shù)值計算，類似于描述性出色的 MATLAB 的編程語言。擴展后的處理語言更適合于行列演算,但基本上和C語言的語風相像，因此可讀性很高。當然，除了Octave以外 MATLAB 和 Scilab 也是非常不錯的語言，但是根據(jù) GPL, Octave 是最容易得到的。
粵公網(wǎng)安備 44010402000282號