Google的-PageRank 意義與解釋(超級網(wǎng)頁等級技術(shù))

本文對作為評價甚高的搜索引擎 Google 的核心技術(shù)之一 PageRank (網(wǎng)頁等級)的基本的概念和評價原理進(jìn)行解釋。

索引

Since: Thu Feb 1 18:22:44 JST 2001
Last Refreshed: Sat Jan 24 18:30:35 JST 2004

★(2007/1/5) 本文的中文版由ROCK翻譯制作完成。

★(2003/7/1) 拙著『Namazu系統(tǒng)的構(gòu)筑和活用』已作修訂。詳情請看介紹頁面。

★(2001/2/28) Namazu 的索引中使用的計算 PageRank 的 Perl 腳本 prnmz-1.0.tar.gz 公開下載。

1.前言

最近，搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于現(xiàn)擔(dān)任 CEO 的 Larry Page 和擔(dān)任總經(jīng)理的 Sergey Brin (2001年2月)在就讀于美斯坦福大學(xué)研究生院時所開發(fā)的搜索引擎的一種檢索服務(wù)。Google 從1998年9月開始服務(wù),但 Netscape Communications 在 Google 的測試階段就開始與其合作，美國 Yahoo! 公司也從2000年6月起將默認(rèn)搜索引擎(美國 Yahoo! 不能檢索時作為增補(bǔ)的搜索引擎)由原先合作的 Inktomi 轉(zhuǎn)換為了 Google。日語版 Google 在2000年9月正式登場,現(xiàn)已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN 和 @NIFTY，7月索尼，2002年1月 Excite 也相繼與 Google 建立了協(xié)作關(guān)系)。

Google 被評價的優(yōu)點(diǎn)不僅僅在于去除無用的(廣告)標(biāo)語構(gòu)成單一頁面的功能、獨(dú)自的 Cache 系統(tǒng)、動態(tài)制成摘要信息、為實現(xiàn)高速檢索而設(shè)置的分散系統(tǒng)(數(shù)千臺規(guī)模的Linux群集器)等，而其中最大的優(yōu)點(diǎn)正是它檢索結(jié)果的正確性。一種能夠自動判斷網(wǎng)頁重要性的技術(shù)「PageRank是(網(wǎng)頁等級)」就是為此而設(shè)計的一種技術(shù)。本文的目的就是以盡可能淺顯易懂的語言來說明 PageRank 系統(tǒng)的概要和原理。

以下是 PageRank 的一篇基礎(chǔ)文章。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

為了更高效地計算 PageRank,以下是改良以后的一篇論文。

Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31

另外，以下是 PageRank 的演示用資料(PowerPoint)。

Larry Page, 'PageRank: Bringing Order to the Web',
http://hci.stanford.edu/~page/papers/pagerank/ （已失效）

接下來就對這兩篇文章(另加一篇資料)進(jìn)行基本說明。首先，用簡單的例子來解說 PageRank 的概念，再歸結(jié)到使用超鏈接關(guān)系的排序系統(tǒng)來解決大規(guī)模疏松疏矩陣的特性值的問題。然后我們會接觸一些在現(xiàn)實世界中應(yīng)用基本模型時出現(xiàn)的問題和對應(yīng)方法。接下來，為了探討是否能夠作為「個人化 PageRank」使用，進(jìn)行對免費(fèi)全文檢索系統(tǒng) Namazu 的安裝實驗并對其結(jié)果進(jìn)行闡述。最后發(fā)表我對 PageRank 的個人見解。

另外，為了能夠理解以下的說明內(nèi)容，需要大學(xué)基礎(chǔ)課程程度的數(shù)學(xué)知識(尤其是線形代數(shù))。然而為使文科生也能夠順利讀下去，盡可能地不用算式來說明問題，同時，為了加入筆者個人的見解，沒有加入像原文那么多的算法和數(shù)字，也存在許多不夠嚴(yán)密和欠正確的地方，事先在次聲明。具體內(nèi)容請參照原文。

PageRank^(TM) 是美國 Google 公司的登記注冊商標(biāo)。

2. PageRank 的基本概念

PageRank 是基于「從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁」的回歸關(guān)系，來判定所有網(wǎng)頁的重要性。

在以下冗長的說明中，許多部分大量地使用了專業(yè)用語，會造成理解上的困難。這一章雖然準(zhǔn)備集中于定性而簡單的解說,但是，即使如此也會有怎么也不明白的時候，此時只要能夠理解「從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁」這一思考方法也就非常得可貴了。因為在所有幾個要點(diǎn)中，這個是最重要的思考方法。

來自于 Google 自己的介紹「Google的受歡迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」是象以下一樣解說的。

關(guān)于PageRank
    PageRank，有效地利用了 Web 所擁有的龐大鏈接構(gòu)造的特性。從網(wǎng)頁A導(dǎo)向網(wǎng)頁B的鏈接被看作是對頁面A對頁面B的支持投票，Google根據(jù)這個投票數(shù)來判斷頁面的重要性。可是 Google 不單單只看投票數(shù)(即鏈接數(shù))，對投票的頁面也進(jìn)行分析�！钢匾浴垢叩捻撁嫠兜钠钡脑u價會更高，因為接受這個投票頁面會被理解為「重要的物品」。
    根據(jù)這樣的分析,得到了高評價的重要頁面會被給予較高的 Page Rank(網(wǎng)頁等級)，在檢索結(jié)果內(nèi)的名次也會提高。PageRank 是 Google 中表示網(wǎng)頁重要性的綜合性指標(biāo)，而且不會受到各種檢索(引擎)的影響。倒不如說，PageRank 就是基于對"使用復(fù)雜的算法而得到的鏈接構(gòu)造"的分析，從而得出的各網(wǎng)頁本身的特性。
    當(dāng)然，重要性高的頁面如果和檢索詞句沒有關(guān)聯(lián)同樣也沒有任何意義。為此 Google 使用了精練后的文本匹配技術(shù)，使得能夠檢索出重要而且正確的頁面。

通過下面的圖我們來具體地看一下剛才所闡述的算法。具體的算法是，將某個頁面的 PageRank 除以存在于這個頁面的正向鏈接,由此得到的值分別和正向鏈接所指向的頁面的 PageRank 相加，即得到了被鏈接的頁面的 PageRank。

PageRank 概念圖。(引自 Page et al.(1998) Figure 2 'Simplified Page Calculation')

讓我們詳細(xì)地看一下。提高 PageRank 的要點(diǎn)，大致有3個。

反向鏈接數(shù) (單純的意義上的受歡迎度指標(biāo))
反向鏈接是否來自推薦度高的頁面 (有根據(jù)的受歡迎指標(biāo))
反向鏈接源頁面的鏈接數(shù) (被選中的幾率指標(biāo))

首先最基本的是，被許多頁面鏈接會使得推薦度提高。也就是說「(被許多頁面鏈接的)受歡迎的頁面，必定是優(yōu)質(zhì)的頁面」。所以以反向鏈接數(shù)作為受歡迎度的一個指標(biāo)是很自然的想法。這是因為，“鏈接”是一種被看作「可以看看這個頁面/這個頁會有用」的推薦行為。但是，值得驕傲的是 PageRank 的思考方法并沒有停留在這個地方。

也就是說，不僅僅是通過反向鏈接數(shù)的多少，還給推薦度較高頁面的反向鏈接以較高的評價。同時，對來自總鏈接數(shù)少頁面的鏈接給予較高的評價，而來自總鏈接數(shù)多的頁面的鏈接給予較低的評價。換句話說「(匯集著許多推薦的)好的頁面所推薦的頁面，必定也是同樣好的頁面」和「與感覺在被胡亂鏈接的鏈接相比，被少數(shù)挑選出的鏈接肯定是優(yōu)質(zhì)的鏈接」這兩種判斷同時進(jìn)行著。一方面，來自他人高水平網(wǎng)頁的正規(guī)鏈接將會被明確重視，另一方面，來自張貼有沒有關(guān)聯(lián)性的類似于書簽的網(wǎng)頁的鏈接會作為「幾乎沒有什么價值(雖然比起不被鏈接來說好一些)」而被輕視。

因此，如果從類似于 Yahoo! 那樣的 PageRank 非常高的站點(diǎn)被鏈接的話，僅此網(wǎng)頁的 PageRank 也會一下子上升；相反地，無論有多少反向鏈接數(shù)，如果全都是從那些沒有多大意義的頁面鏈接過來的話，PageRank 也不會輕易上升。不僅是 Yahoo!, 在某個領(lǐng)域中可以被稱為是有權(quán)威的(或者說固定的)頁面來的反向鏈接是非常有益的。但是，只是一個勁地在自己一些同伴之間制作的鏈接，比如像「單純的內(nèi)部照顧」這樣的做法很難看出有什么價值。也就是說，從注目于全世界所有網(wǎng)頁的視點(diǎn)來判斷(你的網(wǎng)頁)是否真正具有價值。

綜合性地分析這些指標(biāo)，最終形成了將評價較高的頁面顯示在檢索結(jié)果的相對靠前處的搜索結(jié)構(gòu)。

以往的做法只是單純地使用反向鏈接數(shù)來評價頁面的重要性，但 PageRank 所采用方式的優(yōu)點(diǎn)是能夠不受機(jī)械生成的鏈接的影響。也就是說，為了提高 PageRank 需要有優(yōu)質(zhì)頁面的反向鏈接。譬如如果委托 Yahoo! 登陸自己的網(wǎng)站，就會使得 PageRank 驟然上升。但是為此必須致力于制作(網(wǎng)頁的)充實的內(nèi)容。這樣一來，就使得基本上沒有提高 PageRank 的近路(或后門)。不只限于PageRank (Clever 和 HITS 等也同樣)，在利用鏈接構(gòu)造的排序系統(tǒng)中，以前單純的 SPAM 手法將不再通用。這是最大的一個優(yōu)點(diǎn)，也是 Google 方便于使用的最大理由。(雖然是最大的理由,但并不是唯工一的理由。)

在這里請注意，PageRank 自身是由 Google 定量，而與用戶檢索內(nèi)容的表達(dá)式無關(guān)。就像后邊即將闡述的一樣，檢索語句不會呈現(xiàn)在 PageRank 自己的計算式上。不管得到多少的檢索語句，PageRank 也是一定的、文件固有的評分量。

PageRank 的定性說明大致就是這樣一些。但是，為了實際計算排列次序、比較等級，需要更定量性的討論。以下一章將做詳細(xì)的說明。

3.怎樣求得 PageRank

我們感興趣的是，在有像超級鏈接構(gòu)造那樣的互相參照關(guān)系的時候，定量地知道哪一個頁面是最「重要」的。換句話大膽地說，這個也就是嚴(yán)密計算「應(yīng)該從哪一頁開始讀取」這個指標(biāo)的過程。就算從誰都不看的小頁面開始讀取也沒有辦法。

那么，一般地說為了使得像 Web 那樣的超級鏈接構(gòu)造能夠反映在在排列次序上，需要在計算機(jī)上建立超級鏈接構(gòu)造的數(shù)字模型。怎么模型化需要取決于安裝者的方針?biāo)砸桓哦�，但是如果�?yīng)用圖表理論來觀察超級鏈接構(gòu)造的話，最終常�；氐骄€形代數(shù)考慮方法上去。這對于 PageRank 也是一樣的。

計算方法的原理

作為最基本的考慮方法，就是用行列陣的形式來表達(dá)鏈接關(guān)系。從頁面 i 鏈接到另一張頁面 j 的時，將其成分定義為1，反之則定義為 0 。即，行列陣 A 的成分 a_ij 可以用，

  a_ij＝1 if  (從頁面 i 向頁面 j 「 有 」 鏈接的情況) 
      0 if  (從頁面 i 向頁面 j 「沒有」鏈接的情況)

來表示。文件數(shù)用 N 來表示的話，這個行列陣就成為 N×N 的方陣。這個相當(dāng)于在圖表理論中的「鄰接行列」。也就是說，Web 的鏈接關(guān)系可以看做是采用了鄰接關(guān)系有向圖表 S。總而言之，只要建立了鏈接，就應(yīng)該有鄰接關(guān)系。

(*注)由點(diǎn)和點(diǎn)連接的線構(gòu)成的圖形被稱為「圖表(graph)」。這些點(diǎn)被稱為「頂點(diǎn)(vertex)」或者「節(jié)點(diǎn)(node)」；這些線被稱為「邊(edge)」或者「弧(arc)」。圖表分為兩類，“邊”沒有方向的圖表被稱為「無向圖表(undirected graph)」，“邊”帶有方向的圖表被稱為「有向圖表(directed graph)」。把有向圖表想像成單向通行的道路就可以了。圖表能用各種的方法來表示,但一般用在數(shù)據(jù)結(jié)構(gòu)上的是「鄰接行列(adjacency matrix)」和「鄰接列表(adjacency list)」。需要注意的是，如果是無向圖表，鄰接行列 A 就成為了對稱行列,而如果是有向圖表，A 就會成為不對稱行列。

以下是用位圖表示的 Apache 的在線手冊(共128頁)的鄰接行列。當(dāng)黑點(diǎn)呈橫向排列時，表示這個頁面有很多正向鏈接(即向外導(dǎo)出的鏈接)；反之，當(dāng)黑店呈縱向排列時，表示這個頁面有很多反向鏈接。

鄰接行列的例子(采用了Apache 的在線手冊)

PageRank 的行列陣是把這個鄰接行列倒置后(行和列互換)，為了將各列(column)矢量的總和變成 1 (全概率), 把各個列矢量除以各自的鏈接數(shù)(非零要素數(shù))。這樣作成的行列被稱為「推移概率行列」，含有 N 個概率變量，各個行矢量表示狀態(tài)之間的推移概率。倒置的理由是，PageRank 并非重視「鏈接到多少地方」而是重視「被多少地方鏈接」。

PageRank 的計算，就是求屬于這個推移概率行列最大特性值的固有矢量(優(yōu)固有矢量)。

這是因為，當(dāng)線性變換系 t→∞ 漸近時，我們能夠根據(jù)變換行列的"絕對價值最大的特性值"和"屬于它的固有矢量"將其從根本上記述下來。換句話說，用推移概率行列表示的概率過程，是反復(fù)對這個行列進(jìn)行乘法運(yùn)算的一個過程，并且能夠計算出前方狀態(tài)的概率。

再者，雖然聽起來很難,但是求特性值和固有矢量的值是能夠嚴(yán)密分析的一種基礎(chǔ)的數(shù)學(xué)手段。我們能夠自由地給矢量的初始值賦值，但是因為不斷地將行列相乘，得到的矢量卻會集中在一些特定數(shù)值的組合中。我們把那些穩(wěn)定的數(shù)值的組合稱為固有矢量，把固有矢量中特征性的標(biāo)量(scalar)稱為特性值，把這樣的計算方法總稱為分解特性值，把解特性值的問題稱為特性值問題。

(*注) 對 N 次的正方行列 A 把滿足 Ax =λx 的數(shù) λ 稱為 A 的特性值，稱 x 為屬于 λ 的固有矢量。如果你怎么也不能適應(yīng)行列的概念的話，你也可以考慮 N×N 的二元排列就可以了。同時，也可以把矢量考慮成為長度為 N 的普通的(一元)排列就可以了。

簡單的例子

讓我們用簡單的例子來試著逐次計算 PageRank 。首先考慮一下有像下圖表示那樣的鏈接關(guān)系的7個HTML文件。并且，這些HTML文件間的鏈接關(guān)系只是閉合于這1-7的文件中。也就是說，除了這些文檔以外沒有其他任何鏈接的出入。另外請注意，所有的頁面都有正向和反向鏈接(即沒有終點(diǎn))，這也是后面將提出的一個重要假定,在此暫且不深入探討。

表示頁面間互相鏈接關(guān)系的推移圖

首先，把這張推移圖圖表構(gòu)造的鄰接列表表示為排列式，就有以下式子。即，根據(jù)各個鏈接源ID列舉鏈接目標(biāo)的ID。

鏈接源I D 	鏈接目標(biāo) 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 相當(dāng)于線形代數(shù)中的固有矢量，c 相當(dāng)于對應(yīng)特性值的倒數(shù)。為了求得 R ，只要對這個正方行列 M 作特性值分解就可以了。

在分解特性值時有相應(yīng)的各種各樣的數(shù)值分析法,但是本文將不在這里對各種方法詳細(xì)說明，請讀者自己去閱讀一本恰當(dāng)?shù)慕炭茣?在你的暑假里一定有這么一本被埋沒的教科書)。在此，我們就暫且使用決 GNU Octave 這個計算程序?qū)嶋H計算一下特性值和固有矢量。

(*注) GNU Octave ，是支持?jǐn)?shù)值計算，類似于描述性出色的 MATLAB 的編程語言。擴(kuò)展后的處理語言更適合于行列演算,但基本上和C語言的語風(fēng)相像，因此可讀性很高。詳細(xì)請參照 http://www.octave.org/。當(dāng)然，除了Octave以外 MATLAB 和 Scilab 也是非常不錯的語言，但是根據(jù) GPL, Octave 是最容易得到的。

實際舉例

下面我們舉一個實際例子。如果不太明白以下例子在做什么的話，只要認(rèn)為我們能夠使用 Octave 這個程序來解特性值問題即可。

首先，使用恰當(dāng)?shù)木庉嬈髦谱饕韵?Octave 腳本。(在行尾加上分號就能消去多余的結(jié)果輸出，不過，此次為了說明特意去掉了。)

% cat pagerank.m 
#!/usr/bin/octave 
## pagerank.m - 計算 PageRank(TM) 用的簡單的 GNU Octave 腳本

##設(shè)置計時器。 
tic(); 

##　根據(jù)PageRank 的定義，將從文件 i 鏈接到文件 j 的鏈接狀態(tài)的推移概率行列定義為 M(i,j)

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; 
] 
##計算 全部 M 的特性值和固有矢量列的組合。

[V，D]= eig(M)

## 保存與絕對價值最大的特性值對應(yīng)的固有矢量到EigenVector。
    
 EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D))))) 

## PageRank 是將 EigenVector 在概率矢量上標(biāo)準(zhǔn)化后得到的值。
 PageRank = EigenVector．/ norm(EigenVector,1) 
 
## 輸出計算時間。 
elapsed_time = toc()

(2003/7/23:　修正上述腳本的錯誤。)

誤: EigenVector = V(:, find(max(abs(diag(D))))  )
正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D)))))

用 Octave 運(yùn)行這個 pagerank.m 腳本后在標(biāo)準(zhǔn)輸出中得到以下結(jié)果。

% octave pagerank.m 
GNU Octave, version 2.0.16 (i586-redhat-linux-gnu). 
Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton. 
This is free software with ABSOLUTELY NO WARRANTY. 
For details, type `warranty'. 


M =
 
0.00000 1.00000 0.50000 0.00000 0.25000 0.50000 0.00000 
0.20000 0.00000 0.50000 0.33333 0.00000 0.00000 0.00000
0.20000 0.00000 0.00000 0.33333 0.25000 0.00000 0.00000 
0.20000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 
0.20000 0.00000 0.00000 0.33333 0.00000 0.50000 1.00000 
0.00000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 
0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 

V =
 
Columns 1 through 3: 

0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i 
0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 - 0.15402i 
0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i
0.24297 + 0.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i 
0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i 
0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i 
0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722i 

Columns 4 through 6: 

0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i 
0.26420 - 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+ 0.00000i 
-0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + 0.00000i 
-0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + 0.00000i 
0.03106 - 0.35747i 0.03106+ 0.35747i 0.39720 + 0.00000i 

Column 7: 

0.00000 + 0.00000i 
-0.40825 + 0.00000i 
-0.00000 + 0.00000i 
0.00000 + 0.00000i 
-0.00000 + 0.00000i 
0.81650 + 0.00000i
-0.40825 + 0.00000i 

D = 

Columns 1 through 3: 

1.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i -0.44433 + 0.23415i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 - 0.23415i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

Columns 4 through 6: 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.02731 + 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.02731 - 0.31430i 0.00000 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i -0.16595 + 0.00000i 
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

Column 7: 

0.00000 + 0.00000i 
0.00000 + 0.00000i 
0.00000 + 0.00000i 
0.00000 + 0.00000i 
0.00000 + 0.00000i 
0.00000 + 0.00000i 
-0.00000 + 0.00000i 

EigenVector = 
0.69946 
0.38286
0.32396 
0.24297 
0.41231 
0.10308 
0.13989 

PageRank =
0.303514 
0.166134 
0.140575
0.105431 
0.178914 
0.044728 
0.060703 

elapsed_time = 0.063995

Octave 的輸出中，特性值被表示為對角行列 D 的對角成分，各個特性值相對應(yīng)的固有矢量被表示為行列 V 對應(yīng)列的列矢量。也就是說 M * V = D * M 成立。如果包含復(fù)數(shù)特性值的話這里的特性值有7個,其中絕對價值最大的特性值 λ 是λ=1。與之相對應(yīng)的固有矢量為實矢量：

EigenVector = 
	0.69946 
	0.38286 
	0.32396 
	0.24297 
	0.41231 
	0.10308 
	0.13989

即行列 V 的第1列。請注意，這個求得的固有矢量中概率矢量(要素的和等于1的 N 次元非負(fù)矢量)沒有被標(biāo)準(zhǔn)化，只是矢量的「大小」等于 1。用算式來表達(dá)就是，Σp_i ≠1 ，Σ(p_i)²＝1。在這里，對概率矢量進(jìn)行標(biāo)準(zhǔn)化

PageRank 就是排位了。注意，全部相加的和為 1。計算只用了0.064秒。

求得的 PageRank 的評價

將 PageRank 的評價按順序排列 (PageRank 小數(shù)點(diǎn)3位四舍五入)。

名次 PageRank   文件ID    發(fā)出鏈接ID  被鏈接ID
  1     0.304     1       2,3,4,5,7   2,3,5,6
  2     0.179     5       1,3,4,6     1,4,6,7
  3     0.166     2       1           1,3,4
  4     0.141     3       1,2         1,4,5
  5     0.105     4       2,3,5       1,5
  6     0.061     7       5           1
  7     0.045     6       1,5         5

首先應(yīng)該關(guān)注的是，PageRank 的名次和反向鏈接的數(shù)目是基本一致的。無論鏈接多少正向鏈接都幾乎不會影響 PageRank，相反地有多少反向鏈接卻是從根本上決定 PageRank 的大小。但是，僅僅這些并不能說明第1位和第2位之間的顯著差別(同樣地、第3位和第4位，第6位和第7位之間的差別)�？傊�，絕妙之處在于 PageRank 并不只是通過反向鏈接數(shù)來決定的。

讓我們詳細(xì)地看一下。ID=1 的文件的 PageRank 是0.304，占據(jù)全體的三分之一，成為了第1位。特別需要說明的是，起到相當(dāng)大效果的是從排在第3位的 ID=2 頁面中得到了所有的 PageRank(0.166)數(shù)。ID=2頁面有從3個地方過來的反向鏈接，而只有面向 ID=1頁面的一個鏈接，因此(面向ID=1頁面的)鏈接就得到了所有的 PageRank 數(shù)。不過，就因為 ID=1頁面是正向鏈接和反向鏈接最多的頁面，也可以理解它是最受歡迎的頁面吧。

反過來，最后一名的 ID=6 頁面只有 ID=1 的15％的微弱評價,這可以理解為是因為沒有來自 PageRank 很高的 ID=1 的鏈接而使其有很大地影響。總之，即使有同樣的反向鏈接的數(shù)目，鏈接源頁面評價的高低也影響 PageRank 的高低。

表示頁面互相的鏈接關(guān)系的推移圖(加入了PageRank)

實際地試著計算一下PageRank的收支。因為λ=1所以計算很簡單，只要將自各頁的流入量單純相加即可。譬如 ID=1 的流入量為，

流入量＝(ID=2發(fā)出的Rank)+(ID=3發(fā)出的Rank)+(ID=5發(fā)出的Rank)+(ID=6發(fā)出的Rank)
    = 0.166+0.141/2+0.179/4+0.045/2
    = 0.30375

在誤差范圍內(nèi)PageRank的收支相符合。其他頁面ID的情況也一樣。以上的 PageRank 推移圖正表示了這個收支。沿著各自的鏈接發(fā)出的PageRank等于此頁面原有的PageRank除以發(fā)出鏈接數(shù)的值，而且和各自的頁面的PageRank收支相平衡。

不過，這樣絕妙均衡的本身，對理解線形代數(shù)的人來說當(dāng)然不會是讓人驚訝的事情。因為這正是「特性值和固有矢量的性質(zhì)」，總之這樣被選的數(shù)值的組就是固有矢量。但即使是這樣，實際試著確認(rèn)一下的話，已經(jīng)能夠很好地使用PageRank的方法來考慮了。

以上就是 PageRank 的基本原理。 Google 做的就是大規(guī)模地處理這樣的非常特性值問題。

4.實際應(yīng)用時的問題

PageRank 的基本考慮方法并不是很難的東西。實用效果中的巨大成分并不是復(fù)雜離奇的算法，而是進(jìn)行簡單的線性變換，倒不如都屬于簡明直觀的類別吧。但是，實際使用 Web 超級鏈接構(gòu)造來計算 PageRank 的話，不是簡單地能夠用嘴巴來說明的東西。主要的困難主要有二個。一、由來于純粹假設(shè)的數(shù)值模型和現(xiàn)實世界的不同；二，在實際數(shù)值計算上(專門技術(shù)的)困難。

準(zhǔn)備:數(shù)學(xué)用語(主要概率過程)的解說

推移概率行列和概率過程上的馬爾可夫過程存在很深的關(guān)系。本章先離開與 PageRank 本身的說明，預(yù)先說明幾個呈現(xiàn)在概率過程上的數(shù)學(xué)用語。因為會設(shè)計相當(dāng)難的部分，如果不能夠理解也可以跳過這里。(也可能是我的說明方法不好) 同時，請注意這里幾乎沒有證明就直接使用了。詳細(xì)的解說請閱讀教科書。

從有向圖表S的狀態(tài) i 出發(fā)，將有限時間之后再次回復(fù)到狀態(tài) i 的概率作為 1 時，也就是說，當(dāng)沿著(有向)圖表的方向前進(jìn)能夠回到原來位置的路徑存在的時候，i 就被成為「回歸」。不能回歸的狀態(tài)被稱為「非回歸」。從狀態(tài) i 出發(fā)，當(dāng)通過有限次數(shù)的推移達(dá)到狀態(tài) j 的概率非負(fù)的時候，我們就說「從狀態(tài) i 到達(dá)狀態(tài) j 是可能的」。當(dāng)反方向也可能到達(dá)的時候，我們稱「i 和 j 互相可能到達(dá)」。從狀態(tài) i 不能到達(dá)其他任何狀態(tài)的時候，稱 i 為「吸收狀態(tài)」。

從鄰接行列 A 所決定的圖表(graph)的任意頂點(diǎn)出發(fā)，指向其他任意的頂點(diǎn)圖表的路徑能夠像箭頭那樣到達(dá)時被稱為「強(qiáng)聯(lián)結(jié)」( 也被稱為「分解不能」)。強(qiáng)聯(lián)結(jié)，等價于從任意狀態(tài)到任意狀態(tài)可以互相到達(dá)。鄰接行列 A 的成分中有很多 0 時，強(qiáng)聯(lián)結(jié)性就會有問題。注意，如果全部成分都為 a_ij ≠0 的話，則都屬于強(qiáng)聯(lián)結(jié)。因為，對應(yīng)的馬爾可夫鏈的樣本路徑表示 S 的任意兩點(diǎn)間以正的概率來往通行。

我們可以把全體狀態(tài)以等價類(或者回歸類)來劃分。在這里，回歸類是指鏈接所圍成的范圍。屬于一個等價類的狀態(tài)可以互相到達(dá)。從一個類出發(fā)以正的概率進(jìn)入到其他的類的可能性也是存在的。可是很明顯，在這種情況下不可能回復(fù)到原來的類。不然的話，這兩個類就歸于等價類了。下圖表示了，當(dāng) T 作為非回歸性的等價類、R 作為回歸性等價類時,雖然存在 馬爾可夫鏈 既不來自回歸類，也不來自非回歸類的情況，但如果一旦來自前兩者的話，就不再會回到非回歸類中了。

回歸、非回歸示意圖(修改了小谷(1997)的圖11.1)

這個等價關(guān)系中只有一個回歸類的時候，那個馬爾可夫鏈就被稱為「最簡」。換句話說，全部的狀態(tài)之間互相可以到達(dá)時就被稱為最簡。最簡時都是強(qiáng)聯(lián)結(jié)。

互相沒有關(guān)聯(lián)的鄰接行列(或推移概率行列)，乘以恰當(dāng)?shù)闹脫Q行列(掉換行和列)以后得到

P = | P1 0 |
    | 0 P2 |

這樣的關(guān)系。這表示回歸類 P1 和 P2 間不存在直接的鏈接關(guān)系。

回歸類、非回歸類摻雜在一起的鄰接行列(或推移概率行列)，乘以恰當(dāng)?shù)闹脫Q行列后得到，

P = | P1 0 | 
    | Q P2 |

這樣的關(guān)系(Q≠0)。此時，P1是非回歸類，P2是回歸類。

推移概率行列有時也被稱作馬爾可夫行列。稱馬爾可夫過程的試驗行列的觀測結(jié)果為馬爾可夫鏈(Markov chain)。當(dāng)經(jīng)過相當(dāng)?shù)臅r間后馬爾可夫鏈會趨向某種平衡狀態(tài)。對任意的狀態(tài) i, 如果 j 是非回歸狀態(tài)，則 P_ij⁽ⁿ⁾→0。相反，當(dāng) i 為非回歸、j 為回歸時，停留在狀態(tài) i 上著的概率是0。如果 i，j 屬于同樣的非周期性回歸類的話，P_ij⁽ⁿ⁾→P_j≥0。

定理:若 P 是有限馬爾可夫行列的話，P 的特性值 1 的重復(fù)度等于 P 決定的回歸類的數(shù)目。(證明太長，省略)。

跟隨著推移概率行列的有向圖表的最大強(qiáng)聯(lián)結(jié)成分(與之對應(yīng)的狀態(tài)的集合)被稱為Ergodic部分(歷遍部分)，此外的強(qiáng)聯(lián)結(jié)成分被稱為消散部分。因為無論從怎樣的初期狀態(tài)概率 x⁽⁰⁾開始，經(jīng)過時間 n 后 x⁽ⁿ⁾ = P⁽ⁿ⁾x⁽⁰⁾，所以屬于消散部分的狀態(tài)概率幾乎接近于0。關(guān)于EllGoth部分，連同與各聯(lián)結(jié)成分對應(yīng)狀態(tài)的類、像獨(dú)立的最簡的馬爾可夫鏈一樣行動，其中，各類中的狀態(tài)概率(即從過去開始的平均值)的值和初期狀態(tài)概率無關(guān)，換言之，是近似于與對應(yīng) P 的最簡成分的固有矢量成比例的東西。在類之間概率的分配依存于初期狀態(tài)的概率。

離散時間型馬爾可夫鏈的不變分布是屬于極限分布，從那個分布開始已經(jīng)不是在分布意義上的隨時間的變化了。狀態(tài)的概率分布在時間變化時也不會變化時被稱為固定分布。PageRank 用馬爾可夫過程來說就是，PageRank就是以一定時間內(nèi)用戶隨機(jī)地沿著(網(wǎng)頁)鏈接前進(jìn)時對各個頁面訪問的固定分布。

假想模型和現(xiàn)實世界的不同

那么，讓我們將概率過程(即圖表原理)的考慮方法和實際的網(wǎng)頁鏈接構(gòu)造合起來看一看。

對于剛才舉例的假想網(wǎng)頁群來說，只要相互順著鏈接前進(jìn)則在彼此頁面間必定有相互鏈接的關(guān)系。即，有向圖表是強(qiáng)聯(lián)結(jié)的行列既是回歸又是最簡。像上面舉的很多的概率過程的教科書一樣，許多證明都是把回歸和最簡作為前提來證明的，如果是最簡的話，各種各樣的性質(zhì)就變得容易說了。

但是現(xiàn)實的網(wǎng)頁并不是強(qiáng)聯(lián)結(jié)。也就是說鄰接行列不是最簡的。具體來說，順著鏈接前進(jìn)的話，有時會走到?jīng)]有向外鏈接的網(wǎng)頁。通常這樣的情況，只有利用 web 瀏覽器的「返回」功能了。如果人們只是瀏覽而已的話，一切就到此結(jié)束了，然而 PageRank 的計算卻不能到此結(jié)束。因為PageRank 一旦被引入以后是不能返回的。Pagerank 稱這種頁面為為「dangling page」。同樣道理，只有向外的鏈接而沒有反向鏈接的頁面也是存在的。但 Pagerank 并不考慮這樣的頁面,因為沒有流入的 PageRank 而只流出的 PageRank，從對稱性來考慮的話必定是很奇怪的。

同時，有時候也有鏈接只在一個集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接的現(xiàn)象。這是非周期性的回歸類多重存在時可能出現(xiàn)的問題。(請讀者考慮一下陷入上圖中一個 R 中而不能移動到別的 R 和 T 的情況)。 Pagerank 稱之為「rank sink」。在現(xiàn)實中的頁面，無論怎樣順著鏈接前進(jìn)，僅僅順著鏈接是絕對不能進(jìn)入的頁面群總歸存在，也就是說，這些頁面群是從互相沒有關(guān)聯(lián)的多數(shù)的同值類(回歸類)形成的。

總之，由現(xiàn)實的 Web 頁組成的推移概率行列大部分都不是最簡的。當(dāng)不是最簡時，最大特性值(即1)是重復(fù)的，并且不能避免優(yōu)固有矢量多數(shù)存在的問題。換句話說，PageRank 并不是從一個意義上來決定的。

在此，Pagerank 為了解決這樣的問題，考慮了一種「用戶雖然在許多場合都順著當(dāng)前頁面中的鏈接前進(jìn),但時常會跳躍到無關(guān)的頁面里」,這樣的瀏覽模型。再者，將「時常」固定為 15％來計算。用戶在 85％的情況下沿著鏈接前進(jìn),但在 15％的情況下會突然跳躍到無關(guān)的頁面中去。(注:Pagerank 的原始手法是各自87％(＝1/1.15 )和13％(＝0.15/1.15)。)

將此用算式來表示的話得到以下公式。

M'= c*M +(1-c)*[1/N]

其中，[1/N]是所有要素為 1/N 的 N次正方行列，c =0.85(=1-0.15)。M'當(dāng)然也同樣是推移概率行列了。也就是說，根據(jù) Pagerank 的變形，原先求行列 M 的特性值問題變成了求行列 M'的優(yōu)固有矢量特性值問題。M 是固定無記憶信息源(i.i.d.)時，M'被稱為「混合信息源」，這也就是固定但非ellGoth信息源的典型例子。

如果從數(shù)學(xué)角度看，「把非最簡的推移行列最簡化」操作的另外一種說法就是「把不是強(qiáng)聯(lián)結(jié)的圖表變成強(qiáng)聯(lián)結(jié)」的變換操作。所謂對全部的要素都考慮0.15的遷移概率，就是意味著將原本非最簡的推移概率行列轉(zhuǎn)換為最簡并回歸的（當(dāng)然非負(fù)的情況也存在）推移概率行列。針對原本的推移概率行列，進(jìn)行這樣的變換操作的話，就能從一個意義上定義 PageRank、也就是說能保證最大特性值的重復(fù)度為1。如果考慮了這樣的變換操作的話，因為推移概率行列的回歸類的數(shù)目變成 1 的同時也最簡化，根據(jù)前面的定理，優(yōu)固有矢量(即 PageRank)就被從一個意義上定義了。

數(shù)值計算上的問題點(diǎn)(其1)

在此，只要大概明白 PageRank 的概念就可以了，不需要很深的陷入數(shù)值計算上的技術(shù)的問題中(其實，筆者自己即使有自信也說不清楚)。但是，因為特性值分析和聯(lián)立一次方程式分析一樣，是利用在各種的統(tǒng)計分析中重要的數(shù)值計算手法的一中，所以這里我們簡單的觸及一些分析方法。

主記憶領(lǐng)域的問題是在數(shù)值計算上的問題之一。

假設(shè) N 是 10⁴的 order。通常，數(shù)值計算程序內(nèi)部行列和矢量是用雙精度記錄的，N 次正方行列 A 的記憶領(lǐng)域為 sizeof(double)* N * N =8 *10⁴ * 10⁴＝800MB。 800MB 的主記憶領(lǐng)域不是那種經(jīng)常會擁有的東西, 雖然這么說也非那種不可能的數(shù)字。但是，N 如果變成 10⁵ 或10⁶ 的話，各自就變成80GB,8TB。這樣的話不用說內(nèi)存就連硬盤也已經(jīng)很困難了。 Google 從處理著10億以上的頁面(2001年時)以來，就知道這種規(guī)矩的做法已經(jīng)不適用了。

不過，A 只是稀疏(sparse)行列。因為即使有一部分的頁面拼命地進(jìn)行鏈接，但是向整個Web展開鏈接的頁面是沒有的，即使有也是極為稀少的。平均一下，每一張頁面有10-20個左右的鏈接(根據(jù) IBM Almaden 研究所'Graph structure in the web' 的統(tǒng)計，平均在16.1個左右)。因此，我們可以采用恰當(dāng)?shù)膲嚎s方法來壓縮 A 。 N 即使是 10⁶ 時，如果平均鏈接數(shù)是10，最終的記憶領(lǐng)域只要 80MB，從規(guī)模上來說可以收納到合理的數(shù)字里。

稀疏行列的容納方式當(dāng)今已經(jīng)被充分地研究(有限要素法的解法等)，在恰當(dāng)?shù)臄?shù)值計算的專業(yè)書中就可以學(xué)到。雖然這么說，因為相當(dāng)?shù)仉y解還是需要很復(fù)雜的手法。但想指出的是如果可以很好的解決的話，并列化的高速計算(也許)就變得可能了。因為比起怎樣排列并容納非零要素來說，計算性能和并列性能對其的影響會更大。

數(shù)值計算上的問題點(diǎn)(其2)

另一個是收斂問題。

固定方程式

xⁱ＝ΣA_ijx_i

是 N 元的聯(lián)立一次方程式，一般地不能得到分析解，所以只能解其數(shù)值。剛才舉的例子中為了求特性值和固有矢量，使用了 Octave 的 eig()函數(shù), 不過，這個在問題小的時候不能適用。說起來，并不需要計算全部的特性值/固有矢量。

求最大特性值和屬于它的固有矢量(優(yōu)固有矢量)的數(shù)值計算手法中，一般使用「冪乘法」(也叫反復(fù)法)。這是指，取適當(dāng)初期矢量 x⁰ ，當(dāng) x⁽ⁿ⁺¹⁾ = A y⁽ⁿ⁾ (其中 y⁽ⁿ⁾ = x⁽ⁿ⁾ / c⁽ⁿ⁾ )中的 n →∞ 時，x 向擁有最大特性值的固有矢量收斂的同時 c 向此最大特性值收斂的利用線形代數(shù)性質(zhì)的計算方法(證明請參照線形代數(shù)的教科書)。冪乘法(反復(fù)法)的特長與逐次反復(fù)計算的近似法比，能夠改善解矢量的問題。它的優(yōu)點(diǎn)是，因為只要反復(fù)對行列和矢量進(jìn)行適當(dāng)次數(shù)的乘法運(yùn)算，所以只要通過程序就能夠簡單地解決，并且還可以進(jìn)行由于受到內(nèi)存和硬盤的限制通過直接法不能解決的大規(guī)模分析。這是許多的實用算法的出發(fā)點(diǎn)。

在這里，請注意從線形代數(shù)的簡單定理(Peron-Frobenius定理)得到推移概率行列的絕對價值的最大特性值是1。如果采用了這個，就會使得反復(fù)法的

PageRank 的計算變得更容易。即，因為最大特性值是既知的，比起求滿足 Ax=x 的矢量 x來說，變成更加簡單的問題了。這雖然是很細(xì)小的地方但是很重要。首先，可以去掉比較花費(fèi)成本的除法計算 (y⁽ⁿ⁾=x⁽ⁿ⁾/c⁽ⁿ⁾)不用完成。如果是反復(fù)法的話，不能得到很高的精確度，并且如果搞錯了加速方法的話，計算出的不是是最大特性值而是第二大特性值和屬于它的固有矢量(雖然這種情況很少，但是說不定就是從根本上錯誤的值)。但如果知道了最大特性值，就可以進(jìn)行核對了。在 Pagerank 的第一篇論文中他們似乎沒有注意到這個事情,但在 Haveliwala 的第二論文中增加了關(guān)于此的修正。

反復(fù)的次數(shù)取決于想要求的精度。也就是說,想要求的精度越高，反復(fù)的次數(shù)就越多�？墒�，冪乘法(反復(fù)法)的誤差的收斂比與系數(shù)行列的譜段特性(特性值的絕對值分布)有很強(qiáng)的依存關(guān)系。具體地說，絕對值最大的特性值用λ₁表示，第二位用 λ₂ 表示，優(yōu)越率(收斂率 probability of dominance)為 d =λ₁/λ₂ 話，可以知道d離1越近收斂就變得越慢。在 N 很大的情況時d當(dāng)然離1很近。這是因為，絕對值最大的特性值是1，而其他所有的 N-1 個特性值的絕對值都比1小。但是，N-1個特性值之間非常的擁擠，所以λ₁和λ₂ 之間幾乎沒有差別。因此一般來說，收斂會變慢。

所謂收斂變慢，嚴(yán)密地說，就是無論經(jīng)過多少時間也完成不了的計算。對此，為了使收斂加快的適當(dāng)?shù)募铀俜椒ㄒ彩谴嬖诘�，�?yīng)用這些方法時，需要對數(shù)值計算技術(shù)有十二分的理解，因此如果不是數(shù)值計算的專家就很難引入。

5. Namazu 上的實際安裝實驗

為了使更簡單地推測上文描述的問題，PageRank 并不是非世界所有的web頁面而不能使用的考慮方法，即使是個人的利用方法也能實現(xiàn)。為了實現(xiàn)「Personalized PageRank」，針對在各種 UNIX 和 Windows 上運(yùn)作的中小規(guī)模網(wǎng)站適用的全文檢索系統(tǒng) Namazu 進(jìn)行了實際安裝實驗。(關(guān)于Namazu可參考日語全文檢索引擎軟件列表。)

由于實驗?zāi)芎唵蔚乜刂苾?nèi)存的使用量，并將最大特性值用1來考慮，所以將 Have liwala(1999)的想法做為基本的考慮方法。但是對 dangling pages 的處理有少許不同。固有矢量的計算內(nèi)核使用了數(shù)值計算腳本 GNU Octave。所以基本的代碼編寫自己只用了一天就解決了。另外，從用 mknmz 編寫的索引不能直接計算 PageRank，而要事前準(zhǔn)備表示鄰接關(guān)系的索引(鄰接列表)。這個也有可能被編入檢索者(Indexer)的主要部分。

以下表示了實際計算時間(單位：秒)。運(yùn)行機(jī)器的配置為 PentiumII 400MHz x 2,內(nèi)存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般狀態(tài)分發(fā)物)。收斂精度(剩余差矢量的L1規(guī)范)取了到1.0e-10,也許有些過分精確了。

文書數(shù)N     mknmz時間    準(zhǔn)備時間   PageRank計算時間
============================================================
128          58          2          6
2,301       1, 575       46         214
49,604      15,975       478        5,872

因為沒用一些巨大的web頁群來做測試，所以實驗只停留在小規(guī)模的基礎(chǔ)上。雖然有這個難點(diǎn),但從基本上可以了解與索引所花的時間相比，在很短的時間里就可以計算 PageRank 的傾向吧。

因為 Namazu 自身中也有很多難題，所以并不寄予很大的奢望，但至少使用 10⁵ 程度(盡可能 10⁶)規(guī)模的web頁面群來實驗。從趨勢來看可以預(yù)想 N=10⁶ 的計算時間恐怕會發(fā)散開去，所以在 N=10⁶ 時，若是能夠討論把mknmz時間變成和comparable一樣的加速方法的話，對于Personalized PageRank 來說就十分實用了。作為參考，根據(jù)Page et al.(1998)，Google 對7500萬的URL的實際 PageRank 計算時間約是5小時。(2001年2月現(xiàn)在不明)。從這個角度來說，研究更加高效的加速法的余地就十分得必要了吧。

計算實際運(yùn)行時的使用內(nèi)存最大也是10幾MB左右。如果是Haveliwala (1999)那樣的「吝嗇地作戰(zhàn)」的話，最大只有O(3N+2)左右的內(nèi)存使用量就做完了,不過 N 是 10^4-5 程度和內(nèi)存的使用量連 N² 也放不進(jìn)的話，其他的也只能勉強(qiáng)調(diào)諧了，所以以 O(5N+α) (α是疏松行列的非零成分?jǐn)?shù)字，典型的是5-20N左右) 程度來編寫代碼。另外 N 是10³ 左右時，可以確認(rèn)不壓縮疏松行列就在內(nèi)存上使用冪乘法來計算，從速度面上來說是非常有利的。實測時速度為上述數(shù)字的6-7倍左右的。但遺憾的是，這個方法從內(nèi)存的限制來看，盡可能地只使用2-3千頁以內(nèi)。

此次我們使用了 Octave 分發(fā)附屬的「Tsurushi」,不過，正像大家知道的那樣，如果把 Octave 調(diào)諧的好的話，會戲劇性地提高完成的速度。Octave-2.1.x 和 ATLAS 的組合有時候根據(jù)情況甚至?xí)勾笠?guī)模行列乘法的運(yùn)算速度提高10倍以上。

實驗的詳細(xì)結(jié)果請參照prnmz-1.0.tar.gz 中的文檔。

Personalized PageRank 的基本性質(zhì)

人們經(jīng)常會利用 MHonArc、latex2html 或者 PowerPoint 這樣的工具將文檔變成 HTML，針對這樣的人工制作的HTML鏈接群求 PageRank 的話，大部分頁面的得分幾乎都是一樣的(～1/N)。如果考慮鄰接行列，則大部分的成分是1，或者對角成分附近全部是1。因為這樣的推移概率行列的固有矢量成為(1,1,…,1)。

或是象 sitemap.html 一樣變成樹狀的情況下，分?jǐn)?shù)會集中在sitemap.html中。就算占據(jù)全體的9成也不算新奇。

從現(xiàn)在起能說的是，為了計算有意義的 PageRank，要盡可能地排除機(jī)械生成的鏈接關(guān)系。如果把鏈接關(guān)系看做是推薦關(guān)系的話更加容易認(rèn)同了吧。

6.對 PageRank 的個人的見解

(讀者)應(yīng)該沒有余地去懷疑象 PageRank 那樣利用超級鏈接來決定排列次序有效手法吧。

不過，閱讀了這些論文以后筆者自身也考慮了許多問題。在這里，列舉幾個對 PageRank 的個人見解。雖是見解,說到底就是方法論，也許會有很多錯誤的地方。

關(guān)于 dangling page，不相反考慮的原因是什么？

只是因為考慮一定的變異概率時「偶然」會變成最簡才不予考慮嗎？還是有時看漏了什么嗎？稍微有點(diǎn)不太明白。

改善推移概率行列的可能性
說起來，為了保證 PageRank 的單一意義的性質(zhì)(一意)，只要保證推移概率行列是最簡(有向圖表是強(qiáng)聯(lián)結(jié))就行了，沒有必要所有的要素 a_ij 都是非零要素。事實上，像在web上瀏覽 Toyota 汽車網(wǎng)站后緊接著跳向色情網(wǎng)站，接著又繼續(xù)跳到白宮網(wǎng)站瀏覽的怪異的人應(yīng)該是不存在的吧。(請注意這里是指在隨時間變化連續(xù)的形式)。因此，從實用的意義上來說，區(qū)別于改善多少的使用方便程度，應(yīng)該留下對算法改良的余地。
考慮「逗留概率」會怎樣

根據(jù) PageRank 的考慮方法，在一定的時間后必定順著鏈接前進(jìn)到其他的頁面，或者突然怪異的、歪曲的跳到其他頁面。但是如果對照現(xiàn)實的web瀏覽模型，也要考慮一定的逗留概率。具體地說，就是推移概率行列的對角成分中只取( 1-c)/N 的話取得過小了。在原本所有變遷概率都一定的情況下，更加進(jìn)一步分析會怎樣？因為對于無聊的頁面(瀏覽者)必定會想都不想就轉(zhuǎn)到另外的頁面，反過來對于重要的頁面卻會停留較長的時間。

如果考慮概率論應(yīng)用的話必定會考慮其他許多問題

即使是將實現(xiàn)性置之度外，我們也再來試著進(jìn)一步考慮這個想法。概率論中，存在著一種叫消滅概率或叫固定概率的概率。比起 PageRank 的單純而同樣考慮方法，導(dǎo)入這種考慮方法會得到更期望的結(jié)果，所以理所當(dāng)然被大家所期待。大家都知道馬爾可夫鏈中的分枝過程的考慮方法。這是考慮遺傳基因突變時的一個模型，即，說明經(jīng)過一定的時間而產(chǎn)生淘汰的可能性的模型。很多人認(rèn)為這個考慮方法或許會被采用。那么導(dǎo)入帶有限制的概率(禁忌概率)又會怎么樣呢？即，相當(dāng)于導(dǎo)入通過 n 次的推移從狀態(tài) i 移動到狀態(tài) j 時，不經(jīng)過狀態(tài) k 的概率。如果考慮到web瀏覽的性質(zhì)的話，不是也能理所當(dāng)然地成為假定嗎？

不能作為非馬爾可夫過程(或者說 m次的多重馬爾可夫過程)來考慮嗎

所謂馬爾可夫過程，就是與過去的經(jīng)歷無關(guān)，只從現(xiàn)在的狀態(tài)來確定未來的概率法則的概率過程。馬爾可夫過程只依存于1步之前的過程。這個過程和沒有對過去的記憶，沒有依存于過去經(jīng)歷的要素。 PageRank 是在單純馬爾可夫過程隨時間變化而固定的狀態(tài)下計算時候所求得的結(jié)果。但是，人類的理性行動必須以非馬爾可夫過程來表現(xiàn)。復(fù)雜的過程總是以一些形式和過去有著牽連。因此，不僅僅單一地分析從哪個頁面連接來，而要分析沿著怎樣的路徑連接而來的。這樣的分析才會使其有可能成為更有用的排序系統(tǒng)。在能抑制住計算量爆炸的范圍內(nèi)，試著引入非馬爾可夫過程來研究說不定也很有趣。

在考慮到和看到的許許多多中，有像實際安裝那樣不太難的東西，也有因為只是嘴上說說而不知道怎樣實際安裝的東西，不管怎樣，定量地評價它的效果是極為困難的。難道真的是不能實現(xiàn)的東西嗎？

PageRank 的技術(shù)有多少

即使只是采用評價很高的 PageRank 技術(shù)，作為基本的想法也只是使用了枯竭的數(shù)值分析的手法來實現(xiàn)的。但是，象我在這里說明的事情，如果從專業(yè)的研究者來看是理所當(dāng)然的事情了。只是克服規(guī)模這一點(diǎn)就能建立一個專業(yè)的研究領(lǐng)域吧。也可以認(rèn)為專業(yè)領(lǐng)域的內(nèi)部并沒有那么深的盡頭。事實上，我做事，充其量只是表示了「如果是極其小規(guī)模的問題，即使是教科書的手法也能大約地得到滿足計算量的結(jié)果」。

盡管是這樣，充其量只觸及了概要的表面就在嘴邊說「沒什么嘛，原來是程度這么簡單的技術(shù)呀」的那種不懂裝懂的人也是有的。在這里事先強(qiáng)調(diào)：這種淺薄的看法是從根本上錯誤的。

當(dāng)然，PageRank 技巧的非常好的地方是「從許多優(yōu)質(zhì)的頁面連接過來的頁面是還是優(yōu)質(zhì)的頁面」，如果明白了就會覺得是簡單的想法。但更進(jìn)一步說，真正絕妙的地方是，不僅僅只是想到一個主意，而是將想法用固定狀態(tài)變遷的概率分布來定式化，為了實證其有效性而實際地進(jìn)行安裝實驗，并證明其在現(xiàn)實領(lǐng)域也能很好地運(yùn)作的過程。在所有的這些階段都成功了才是真正值得被稱贊的。

的確，不僅有斬新而且巧妙的想法，再加上結(jié)合教科書的手法，也有可能制造出能和 Google 匹敵(或是凌駕)的搜索引擎。也可以說實際上 Google 自己也在這么做著。但是，實際完成的人卻是少得驚人。假想模型中的「肯定能夠完成」的東西和實際運(yùn)作的東西之間有著天差地別。在實際問題上，處理大規(guī)模疏松行列本身，通過一般的手法也是相當(dāng)?shù)睦щy，需要高度的專業(yè)技術(shù)。應(yīng)該銘記在頭腦中總覺得能夠理解的事和實現(xiàn)中能夠做的事之間絕對會有不能填埋的差距。不可過分輕率地考慮。

7.參考文獻(xiàn)

以下列舉了除了在「前言」中介紹的基本論文以外的關(guān)聯(lián)論文。(譯者去掉了許多無用的連接)

S. Brin, L. Page, 'The Anatomy of a Large-Scale Hypertextual Web Search Engine', http://www-db.stanford.edu/~backrub/google.html
山名早人，近藤秀和，「解說:搜索引擎Google」(概要) , 信息處理42卷8號(2001年8月), pp.775-780 (PDF)
原田昌紀(jì)，「路標(biāo):WWW搜索引擎的建立方法」(概要), 信息處理41卷11號(2000年11月), pp.1280-1283
原田昌紀(jì)，「搜索引擎檢索結(jié)果的排序」,bit 2000年8月號(Vol.32), pp.8-14
美國 Clever Project，「聰明地使用超級鏈接」 (概要) ,日經(jīng)科學(xué) 1999年9月號, pp.28-35
Dell Zhang, Yisheng Dong, 'An Efficient Algorithm to Rank Web Resources', http://www9.org/w9cdrom/251/251.html
Jon M. Kleinberg, 'Authoritative sources in a hyperlinked environment', Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. http://www.cs.cornell.edu/home/kleinber/auth.ps
IBM Almaden Research Center, 'CLEVER Searching', http://www.almaden.ibm.com/cs/k53/clever.html

以下列舉數(shù)學(xué)關(guān)聯(lián)的參考書籍。

S．卡琳著，佐藤健一，佐藤由身子譯，『概率過程講義』(數(shù)理分析與周邊3),1974年，產(chǎn)業(yè)圖書
巖堀信子著，『圖表和概率過程』 (與數(shù)理分析與周邊4),1974年，產(chǎn)業(yè)圖書
伊藤升他著，『經(jīng)濟(jì)系、工學(xué)系的行列及應(yīng)用』, 1987年，紀(jì)伊國屋書店, ISBN4-314-00477-0
L.V.Atokinson, P.J.哈里, J.D.赫德森共著，神谷紀(jì)生，大野信忠，佐脅豐，北榮輔合譯，『數(shù)值計算及其應(yīng)用- FORTRAN77-』, 1993年，Science公司，ISBN4-7819-0690-7
宮澤政清著，『概率和概率過程』(現(xiàn)代數(shù)學(xué)研究小組17),1993年，近代科學(xué)社， ISBN4-7649-1034-9
伊理正夫著，『線形代數(shù)II』(巖波講座應(yīng)用數(shù)學(xué)11) ,1994年，巖波書店, ISBN4-00-010521-3
韓太舜，小林欣吾著，『信息和符號化數(shù)理』(巖波講座應(yīng)用數(shù)學(xué)13) ,1994年，巖波書店, ISBN4-00-010523-X
小國力著，『MATLAB及其實際利用-現(xiàn)代應(yīng)用數(shù)學(xué)和CG -』( Information & Computing=86),1995年，Science公司， ISBN4-7819-0763-6
長谷川里美，長谷川秀彥，藤野清次譯，『反復(fù)法 Templates』(應(yīng)用數(shù)值計算Library),1996年，朝倉書店, ISBN4-254-11401-X
小谷真一著，『測每次和概率2』(巖波講座現(xiàn)代數(shù)學(xué)基礎(chǔ)10 ),1997年，巖波書店, ISBN4-00-010640-6
藤野清次著，『數(shù)值計算之基礎(chǔ)-以數(shù)值解法做為中心』(Library新信息工程之基礎(chǔ)9),1998年，Science公司，ISBN4-7819-0861-6

與有關(guān) Google 的在線新聞報道(日語新聞)已經(jīng)分離到其另一張頁面(googlenews.html) 。(2003/5/20)

其他，特別列出幾個認(rèn)為有關(guān)聯(lián)的頁面。

Interview with Google's Sergey Brin(翻譯報道) (LinuxGazette)
Web搜索引擎的商務(wù)模型和檢索技術(shù)動向-以Google為例- (JCOT報告)
聰明地分開使用吧!　21世紀(jì)的搜索引擎(InternetWatch)
Web的「地圖」的研究成果公布。10％沒有被鏈接 (InternetWatch)
站點(diǎn)研究結(jié)果「搜索引擎之檢索到了一部分」 (HotWired Japan)
檢索引擎的檢索結(jié)果不平等 (HotWired Japan)
Google --停住時代，你是美麗的--(yomoyomo 氏族)
Google Weblog (Japanese Version)
Patent Death Pending (the cluetrain weblog)
Google's PageRank: Calculator (Web Workshop)

感謝轉(zhuǎn)載！其他許多的個人站點(diǎn)和BBS都介紹了此文。

ZDNet China中文如何提高網(wǎng)站在Google中的排名(2003/1/6報道) 。讀不了... :-)
ZDNet China 如何評價一個網(wǎng)站的人氣(2002/8/5報道) 還是中文。讀不懂... :-)
中村正三郎「BRAVO! Linux」Linux Japan 2001年5月號
InternetWatch Watcher選出的今天的站點(diǎn)2001年3月16日號
InternetWatch 摘要新聞2001年2月26日號
Google World > Japanese >計算機(jī)>因特網(wǎng)> WWW >主頁檢索目錄
Lycos /計算機(jī)、因特網(wǎng)/因特網(wǎng)/站點(diǎn)的檢索、鏈接集/搜索引擎/機(jī)器人檢索/ Google 目錄
Yahoo! JAPAN 商務(wù)經(jīng)濟(jì)>企業(yè)>因特網(wǎng)服務(wù)>企業(yè)間交易(BtoB)>檢索，導(dǎo)航> Google 目錄

8.附錄:「guguru？/ goguru?」

英語(美式英語)中是不可能把 Google 念成「goguru」的。和沒有人把拉面的 noodle 發(fā)音或標(biāo)記為「nodoru」一樣，如果硬要用片假名來表示的話應(yīng)該寫成「グーグル」。

不過，有oo 這個拼寫的英文單詞有以下這些。

book, bool, cook, cool, food, good, hook, look, loop, loose, mood, moon, noon, pool, roof, soon, tool, wood, zoo, ...

這些都是簡單的一般的英文單詞,但不論取哪個都有「u:」這個發(fā)音。至少，對許多的典型的日本人來說聽起來是這樣的吧。英語(美式英語)，oo 的拼寫基本讀成「u」。當(dāng)然，goo就讀成「gu:」。廣末涼子不也在中古車信息雜志的電視廣告中說「如果要說車，gu―」嗎？另外，游泳時使用游泳眼鏡的拼寫是 goggle。

當(dāng)然，如果 Google 不是英語(美式英語)話那就另當(dāng)別論了。但是，Google 名字的由來是從表示10的100次方的英文單詞「googol」而來的，也許還是英語發(fā)音比較適合(google)吧。不用說，googol 的發(fā)音也是「guguru」吧。

另外，創(chuàng)業(yè)者之一是 Sergey Brin，從他的名字就能明白他是俄羅斯出身，也有可能是他的英語發(fā)音帶有自己的方言。如果扯到那里的話，已經(jīng)是牽強(qiáng)附會了。而且，我也不太清楚Google 用俄羅斯的地方口音怎么發(fā)音。如果有識之士在的話，請一定告訴我。

補(bǔ)充(2001/4): 給Google的支持中心發(fā)了「是goguru,還是guguru？」的詢問信的一位讀者，熱情地給我轉(zhuǎn)發(fā)了這封郵件。對方說雖然 Google 自己本身的發(fā)音是「guguru」,不過，你以你自己喜歡的叫法稱呼也決不會介意的哦。

Date: Wed,31 Jan 200116:12:01-0800
From:”GoogleTech”<googletech＠google.com>
Subject: RE:{Google#034-917 } pronunciation
To:轉(zhuǎn)送郵件者(Thanks)!

We go by:”GU Gul” 

But you are welcome to say whichever you prefer! 

Regards， 
The Google Team

補(bǔ)充2(2001/10/29):請看Google的頁面 ”Google”怎么發(fā)音。