Google的-PageRank 意義與解釋(超級網頁等級技術)

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

索引

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系統的構筑和活用』已作修訂。詳情請看介紹頁面。

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

1.前言

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

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

以下是 PageRank 的一篇基礎文章。

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/ （已失效）

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

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

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

2. PageRank 的基本概念

PageRank 是基于「從許多優質的網頁鏈接過來的網頁，必定還是優質網頁」的回歸關系，來判定所有網頁的重要性。

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

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

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

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

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

讓我們詳細地看一下。提高 PageRank 的要點，大致有3個。

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

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

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

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

綜合性地分析這些指標，最終形成了將評價較高的頁面顯示在檢索結果的相對靠前處的搜索結構。

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

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

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

3.怎樣求得 PageRank

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

那么，一般地說為了使得像 Web 那樣的超級鏈接構造能夠反映在在排列次序上，需要在計算機上建立超級鏈接構造的數字模型。怎么模型化需要取決于安裝者的方針所以一概而論，但是如果應用圖表理論來觀察超級鏈接構造的話，最終常?；氐骄€形代數考慮方法上去。這對于 PageRank 也是一樣的。

計算方法的原理

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

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

來表示。文件數用 N 來表示的話，這個行列陣就成為 N×N 的方陣。這個相當于在圖表理論中的「鄰接行列」。也就是說，Web 的鏈接關系可以看做是采用了鄰接關系有向圖表 S?？偠灾?，只要建立了鏈接，就應該有鄰接關系。

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

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

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

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

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

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

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

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

簡單的例子

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

表示頁面間互相鏈接關系的推移圖

首先，把這張推移圖圖表構造的鄰接列表表示為排列式，就有以下式子。即，根據各個鏈接源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

以這個鄰接列表中所表示的鏈接關系的鄰接行列 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 倒置后將各個數值除以各自的非零要素后得到的。即以下這個 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 (各個的頁面的等級數的隊列)，存在著 R = cMR 的關系(c 為定量)。在這種情況下，R 相當于線形代數中的固有矢量，c 相當于對應特性值的倒數。為了求得 R ，只要對這個正方行列 M 作特性值分解就可以了。

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

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

實際舉例

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

首先，使用恰當的編輯器制作以下 Octave 腳本。(在行尾加上分號就能消去多余的結果輸出，不過，此次為了說明特意去掉了。)

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

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

##　根據PageRank 的定義，將從文件 i 鏈接到文件 j 的鏈接狀態的推移概率行列定義為 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)

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

## PageRank 是將 EigenVector 在概率矢量上標準化后得到的值。
 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 運行這個 pagerank.m 腳本后在標準輸出中得到以下結果。

% 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 的對角成分，各個特性值相對應的固有矢量被表示為行列 V 對應列的列矢量。也就是說 M * V = D * M 成立。如果包含復數特性值的話這里的特性值有7個,其中絕對價值最大的特性值 λ 是λ=1。與之相對應的固有矢量為實矢量：

EigenVector = 
	0.69946 
	0.38286 
	0.32396 
	0.24297 
	0.41231 
	0.10308 
	0.13989

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

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

求得的 PageRank 的評價

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

名次 PageRank   文件ID    發出鏈接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

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

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

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

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

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

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

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

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

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

4.實際應用時的問題

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

準備:數學用語(主要概率過程)的解說

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

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

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

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

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

這個等價關系中只有一個回歸類的時候，那個馬爾可夫鏈就被稱為「最簡」。換句話說，全部的狀態之間互相可以到達時就被稱為最簡。最簡時都是強聯結。

互相完全沒有關聯的鄰接行列(或推移概率行列)，乘以恰當的置換行列(掉換行和列)以后得到

P = | P1 0 |
    | 0 P2 |

這樣的關系。這表示回歸類 P1 和 P2 間完全不存在直接的鏈接關系。

回歸類、非回歸類摻雜在一起的鄰接行列(或推移概率行列)，乘以恰當的置換行列后得到，

P = | P1 0 | 
    | Q P2 |

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

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

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

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

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

假想模型和現實世界的不同

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

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

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

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

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

在此，Pagerank 為了解決這樣的問題，考慮了一種「用戶雖然在許多場合都順著當前頁面中的鏈接前進,但時常會跳躍到完全無關的頁面里」,這樣的瀏覽模型。再者，將「時?！构潭? 15％來計算。用戶在 85％的情況下沿著鏈接前進,但在 15％的情況下會突然跳躍到無關的頁面中去。(注: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'當然也同樣是推移概率行列了。也就是說，根據 Pagerank 的變形，原先求行列 M 的特性值問題變成了求行列 M'的優固有矢量特性值問題。M 是固定無記憶信息源(i.i.d.)時，M'被稱為「混合信息源」，這也就是固定但非ellGoth信息源的典型例子。

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

數值計算上的問題點(其1)

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

主記憶領域的問題是在數值計算上的問題之一。

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

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

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

數值計算上的問題點(其2)

另一個是收斂問題。

固定方程式

xⁱ＝ΣA_ijx_i

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

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

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

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

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

所謂收斂變慢，嚴密地說，就是無論經過多少時間也完成不了的計算。對此，為了使收斂加快的適當的加速方法也是存在的，應用這些方法時，需要對數值計算技術有十二分的理解，因此如果不是數值計算的專家就很難引入。

5. Namazu 上的實際安裝實驗

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

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

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

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

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

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

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

此次我們使用了 Octave 分發附屬的「Tsurushi」,不過，正像大家知道的那樣，如果把 Octave 調諧的好的話，會戲劇性地提高完成的速度。Octave-2.1.x 和 ATLAS 的組合有時候根據情況甚至會使大規模行列乘法的運算速度提高10倍以上。

實驗的詳細結果請參照prnmz-1.0.tar.gz 中的文檔。

Personalized PageRank 的基本性質

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

或是象 sitemap.html 一樣變成樹狀的情況下，分數會集中在sitemap.html中。就算占據全體的9成也不算新奇。

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

6.對 PageRank 的個人的見解

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

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

關于 dangling page，不相反考慮的原因是什么？

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

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

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

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

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

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

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

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

PageRank 的技術有多少

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

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

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

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

7.參考文獻

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

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)
原田昌紀，「路標:WWW搜索引擎的建立方法」(概要), 信息處理41卷11號(2000年11月), pp.1280-1283
原田昌紀，「搜索引擎檢索結果的排序」,bit 2000年8月號(Vol.32), pp.8-14
美國 Clever Project，「聰明地使用超級鏈接」 (概要) ,日經科學 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

以下列舉數學關聯的參考書籍。

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

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

其他，特別列出幾個認為有關聯的頁面。

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

感謝轉載！其他許多的個人站點和BBS都介紹了此文。

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

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

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

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

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

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

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

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

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

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

We go by:”GU Gul” 

But you are welcome to say whichever you prefer! 

Regards， 
The Google Team

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

在线日韩av免费永久观看,国产精品乱码在线观看,2012中文字幕电影中文字幕在线,精品伊人久久久99热这里只