1、/bqipd/seopages/pagerank.html我們感興趣的是，在有像超級鏈接構造那樣的互相參照關系的時候，定量地 知道哪一個頁面是最重要的。換句話大膽地說，這個也就是嚴密計算應該 從哪一頁開始讀取這個指標的過程。就算從誰都不看的小頁面開始讀取也沒有 辦法。那么，一般地說為了使得像 Web 那樣的超級鏈接構造能夠反映在在排列次 序上，需要在計算機上建立超級鏈接構造的數字模型。 怎么模型化需要取決于 安裝者的方針所以一概而論，但是如果應用圖表理論來觀察超級鏈接構造的話， 最終常常回到線形代數考慮方法上去。這對于 PageRank 也是一樣的。計算方法的原理作為最基本的考慮方法，就是用行

2、列陣的形式來表達鏈接關系。從頁面 i 鏈 接到另一張頁面 j 的時，將其成分定義為1，反之則定義為 0 。即，行列陣 A 的成分 aij 可以用，aij = l if （從頁面i向頁面j 有鏈接的情況）0 if （從頁面i向頁面j 沒有鏈接的情況）來表示。文件數用N來表示的話，這個行列陣就成為NXN的方陣。這個 相當于在圖表理論中的鄰接行列。也就是說,Web的鏈接關系可以看做是采 用了鄰接關系有向圖表S。總而言之，只要建立了鏈接，就應該有鄰接關系。(*注)由點和點連接的線構成的圖形被稱為圖表(graph)。這些點被稱為頂點(vertex)或者節點(node)；這些線被稱為邊(edge)或者弧(

3、arc)。 圖表分為兩類，“邊”沒有方向的圖表被稱為無向圖表(undirected graph)，“邊”帶有方向的圖表被稱為有向圖表(directed graph)。把有向圖表想像 成單向通行的道路就可以了。圖表能用各種的方法來表示,但一般用在數據結構 上的是鄰接行列(adjacency matrix)和鄰接列表(adjacency list)。需 要注意的是，如果是無向圖表，鄰接行列 A 就成為了對稱行列,而如果是有向圖 表， A 就會成為不對稱行列。以下是用位圖表示的 Apache 的在線手冊(共128頁)的鄰接行列。當黑點呈 橫向排列時，表示這個頁面有很多正向鏈接(即向外導出的鏈接)；反

4、之，當黑店 呈縱向排列時，表示這個頁面有很多反向鏈接。鄰接行列的例子PageRank 的行列陣是把這個鄰接行列倒置后（行和列互換），為了將各列 （column）矢量的總和變成1 （全概率），把各個列矢量除以各自的鏈接數（非零 要素數）。這樣作成的行列被稱為推移概率行列，含有 N 個概率變量，各個 行矢量表示狀態之間的推移概率。倒置的理由是，PageRank并非重視鏈接到 多少地方而是重視被多少地方鏈接。PageRank 的計算，就是求屬于這個推移概率行列最大特性值的固有矢量（優 固有矢量）。這是因為，當線性變換系t8漸近時，我們能夠根據變換行列的絕對價 值最大的特性值和屬于它的固有矢量將其從根

5、本上記述下來。換句話說，用 推移概率行列表示的概率過程，是反復對這個行列進行乘法運算的一個過程，并 且能夠計算出前方狀態的概率。再者，雖然聽起來很難,但是求特性值和固有矢量的值是能夠嚴密分析的一 種基礎的數學手段。我們能夠自由地給矢量的初始值賦值，但是因為不斷地將行 列相乘，得到的矢量卻會集中在一些特定數值的組合中。我們把那些穩定的數值 的組合稱為固有矢量，把固有矢量中特征性的標量（scalar）稱為特性值，把這樣 的計算方法總稱為分解特性值，把解特性值的問題稱為特性值問題。（*注）對N次的正方行列A把滿足Ax二入x的數入 稱為A的特性值， 稱x為屬于入 的固有矢量。如果你怎么也不能適應行列的

6、概念的話，你也可 以考慮NXN的二元排列就可以了。同時，也可以把矢量考慮成為長度為N的 普通的（一元）排列就可以了。簡單的例子讓我們用簡單的例子來試著逐次計算 PageRank 。首先考慮一下有像下圖表 示那樣的鏈接關系的7個HTML文件。并且，這些HTML文件間的鏈接關系只是閉 合于這1-7的文件中。也就是說，除了這些文檔以外沒有其他任何鏈接的出入。 另外請注意，所有的頁面都有正向和反向鏈接（即沒有終點），這也是后面將提出 的一個重要假定,在此暫且不深入探討。首先，把這張推移圖圖表構造的鄰接列表表示為排列式，就有以下式子。即， 根據各個鏈接源ID列舉鏈接目標的ID。鏈接源I D 鏈接目標ID

7、2,3 ,4,5, 7 TOC o 1-5 h z 11,22,3,51,3,4,61,55以這個鄰接列表中所表示的鏈接關系的鄰接行列A是以下這樣的7X7的 正方行列。一個僅有要素0和1位圖行列（bitmapmatrix）。橫向查看第i行 表示從文件i正向鏈接的文件ID。A = TOC o 1-5 h z 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 倒置后將各個數值除以各自的非 零要素后得到的

8、。即以下這個7X7的正方行列。橫向查看第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 （各個的頁面的等級數的隊列），存在著 R = cMR 的關系（C為定量）。在這種情況下，R相當于線形代數中的固有矢量，c相當于對應特

9、性值的倒數。為了求得 R ，只要對這個正方行列 M 作特性值分解就可以 了。在分解特性值時有相應的各種各樣的數值分析法,但是本文將不在這里對各 種方法詳細說明，請讀者自己去閱讀一本恰當的教科書(在你的暑假里一定有這 么一本被埋沒的教科書)。在此，我們就暫且使用決 GNU Octave 這個計算程序 實際計算一下特性值和固有矢量。(*注) GNU Octave ，是支持數值計算，類似于描述性出色的 MATLAB 的編 程語言。擴展后的處理語言更適合于行列演算,但基本上和 C 語言的語風相像， 因此可讀性很高。詳細請參照 HYPERLINK /%e3%80%82 /。 當然，除了 Octave 以

10、外 MATLAB 和 Scilab 也是非常不錯的語言，但是根據 GPL, Octave 是最容 易得到的。實際舉例下面我們舉一個實際例子。如果不太明白以下例子在做什么的話，只要認為 我們能夠使用 Octave 這個程序來解特性值問題即可。首先，使用恰當的編輯器制作以下 Octave 腳本。(在行尾加上分號就能消 去多余的結果輸出，不過，此次為了說明特意去掉了。)% cat pagerank.m#!/usr/bin/octave# pagerank.m -計算 PageRank(TM)用的簡單的 GNU Octave 腳本#設置計時器。tic();#根據PageRank的定義，將從文件i鏈接到

11、文件j的鏈接狀態的推移概率 行列定義為M(i,j)0,1,0,1,1/2,0,1/4,1/5,0,1/2,1/3,0,1/5,0,0,1/3,1/4,1/5,0,0,0,1/4,1/5,0,0,1/3,0,0,0,0,0,1/4,1/5,0,0,0,0,1/2 ,0;0,0；0,0;0,0;1/2,1;0,0;0,0;#計算 全部M的特性值和固有矢量列的組合。V, D= eig(M)#保存與絕對價值最大的特性值對應的固有矢量到EigenVector。EigenVec tor = V(:, find(abs(diag(D)二二max(abs(diag(D)# PageRank是將EigenVec

12、tor在概率矢量上標準化后得到的值。PageRank = EigenVector. / norm(EigenVector,1)#輸出計算時間。elapsed _time = to c()用 Octave 運行這個 pagerank.m 腳本后在標準輸出中得到以下結果。% oct ave pagerank.mGNU Oct ave, version 2.0.16 (i586-redha t-li nux-gnu).Copyrigh t (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton.This is free software with ABSOLUT

13、ELY NO WARRANTY.For details, type warranty.M =0.00000 1.000000.500000.000000.250000.500000.000000.20000 0.000000.500000.333330.000000.000000.000000.20000 0.000000.000000.333330.250000.000000.000000.20000 0.000000.000000.000000.250000.000000.000000.20000 0.000000.000000.333330.000000.500001.000000.00

14、000 0.000000.000000.000000.250000.000000.000000.20000 0.000000.000000.000000.000000.000000.00000V =Columns 1 through 3:0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 0.15402i0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i0.24297 + 0

15、.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722iColumns 4 through 6:0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i0.26420

16、 - 0.05040i 0.26420 + 0.05040i 0.14584 + 0.00000i-0.10267 + 0.14787i -0.10267- 0.14787i 0.24608 + 0.00000i-0.11643 + 0.02319i -0.11643 0.02319i -0.24398+ O.OOOOOi-0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + O.OOOOOi-0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + O.OOOOOi0.03106 - 0.35747i 0.0

17、3106+ 0.35747i 0.39720 + O.OOOOOiColumn 7:0.00000 + O.OOOOOi-0.40825 + O.OOOOOi-0.00000 + O.OOOOOi0.00000 + O.OOOOOi-0.00000 + O.OOOOOi0.81650 + O.OOOOOi-0.40825 + O.OOOOOiD =Columns 1 through 3:1.00000 + O.OOOOOi 0.00000 + O.OOOOOi 0.00000 + O.OOOOOi0.00000 + O.OOOOOi -0.44433 + 0.23415i 0.00000 +

18、O.OOOOOi0.00000 + O.OOOOOi 0.00000 + O.OOOOOi -0.44433 - 0.23415i0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOi0.00000+O.OOOOOiColumns 4 through 6:0.00000 + O.OOOOOi0.000

19、00 + O.OOOOOi0.00000 + 0.00000i0.00000 + 0.00000i0.02731 + 0.31430i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000iColumn 7:0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i-0.00000 + 0.00000iEigenVector =0.699460.382860.323960.242970.

20、412310.103080.13989PageRank =0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.02731 - 0.31430i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i0.00000 + 0.00000i-0.16595 + 0.00000i0.00000 + 0.00000i0.3035140.1661340.

21、1405750.1054310.1789140.0447280.060703elapsed_time = 0.063995Octave 的輸出中，特性值被表示為對角行列 D 的對角成分，各個特性值相 對應的固有矢量被表示為行列V對應列的列矢量。也就是說M * V = D * M成 立。如果包含復數特性值的話這里的特性值有7個,其中絕對價值最大的特性值 入 是入=1。與之相對應的固有矢量為實矢量：EigenVector =0.699460.382860.323960.242970.412310.103080.13989即行列 V 的第1列。請注意，這個求得的固有矢量中概率矢量（要素的和等 于1的

22、 N 次元非負矢量）沒有被標準化，只是矢量的大小等于 1。 用算式 來表達就是，工pi工1 ,工（pi）2 = 1。在這里，對概率矢量進行標準化PageRank =0.3035140.1661340.1405750.1054310.1789140.0447280.060703PageRank 就是排位了。 注意，全部相加的和為 1。 計算只用了 0.064 秒求得的 PageRank 的評價將 PageRank 的評價按順序排列 （PageRank 小數點 3 位四舍五入 ） 。名次PageRank文件ID發出鏈接ID被鏈接ID10.30412,3,4,5,72,3,5,620.17951,3

23、,4,61,4,6,730.166211,3,440.14131,21,4,550.10542,3,51,560.06175170.04561,55首先應該關注的是，PageRank的名次和反向鏈接的數目是基本一致的。無 論鏈接多少正向鏈接都幾乎不會影響PageRank，相反地有多少反向鏈接卻是從 根本上決定 PageRank 的大小。但是，僅僅這些并不能說明第1位和第2位之間 的顯著差別（同樣地、第3位和第4位，第6位和第7位之間的差別）。總之，絕 妙之處在于 PageRank 并不只是通過反向鏈接數來決定的。讓我們詳細地看一下。 ID=1 的文件的 PageRank 是0.304，占據全體的三 分之一，成為了第1位。特別需要說明的是，起到相當大效果的是從排在第3 位的