1.Google PageRank 算法

1.1、PageRank(網(wǎng)頁(yè)級(jí)別)的概念
    互聯(lián)網(wǎng)發(fā)展早期的搜索引擎，對(duì)web頁(yè)面的排序，是根據(jù)搜索的詞組（短語(yǔ)）在頁(yè)面中的出現(xiàn)次數(shù)（occurence ），并用頁(yè)面長(zhǎng)度和html標(biāo)簽的重要性提示等進(jìn)行權(quán)重修訂。鏈接名氣(link popularity)技術(shù)通過(guò)其它文檔鏈接到當(dāng)前頁(yè)面（inbound links）的鏈接數(shù)量來(lái)決定當(dāng)前頁(yè)的重要性，這樣可以有效地抵制被人為加工的頁(yè)面欺騙搜索引擎的手法。

          PageRank計(jì)算頁(yè)面的重要性，對(duì)每個(gè)鏈入(inbound)賦以不同的權(quán)值，鏈接提供頁(yè)面的越重要?jiǎng)t此鏈接入越高。當(dāng)前頁(yè)的重要性，是由其它頁(yè)面的重要性決定的。

1.2、PageRank算法1

　　PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中：PR(A):頁(yè)面A的網(wǎng)頁(yè)級(jí)別,
PR(Ti)：頁(yè)面Ti的網(wǎng)頁(yè)級(jí)別，頁(yè)面Ti鏈向頁(yè)面A，
C(Ti)：頁(yè)面Ti鏈出的鏈接數(shù)量，
d：阻尼系數(shù)，取值在0－1之間.

由此可見(jiàn)，1）這個(gè)算法不以站點(diǎn)排序，頁(yè)面網(wǎng)頁(yè)級(jí)別由一個(gè)個(gè)獨(dú)立的頁(yè)面決定；2）頁(yè)面的網(wǎng)頁(yè)級(jí)別由鏈向它的頁(yè)面的網(wǎng)頁(yè)級(jí)別決定，但每個(gè)鏈入頁(yè)面的貢獻(xiàn)的值是不同的。如果Ti頁(yè)面中鏈出越多，它對(duì)當(dāng)前頁(yè)面A的貢獻(xiàn)就越小。A的鏈入頁(yè)面越多，其網(wǎng)頁(yè)級(jí)別也越高；3）阻尼系數(shù)的使用，減少了其它頁(yè)面對(duì)當(dāng)前頁(yè)面A的排序貢獻(xiàn)。

1.3、隨機(jī)沖浪模型
　　Lawrence Page 和 Sergey Brin 提出了用戶(hù)行為的隨機(jī)沖浪模型，來(lái)解釋上述算法。他們把用戶(hù)點(diǎn)擊鏈接的行為，視為一種不關(guān)心內(nèi)容的隨機(jī)行為。而用戶(hù)點(diǎn)擊頁(yè)面內(nèi)的鏈接的概率，完全由頁(yè)面上鏈接數(shù)量的多少?zèng)Q定的，這也是上面PR(Ti)/C(Ti)的原因。一個(gè)頁(yè)面通過(guò)隨機(jī)沖浪到達(dá)的概率就是鏈入它的別的頁(yè)面上的鏈接的被點(diǎn)擊概率的和。阻尼系數(shù)d的引入，是因?yàn)橛脩?hù)不可能無(wú)限的點(diǎn)擊鏈接，常常因勞累而隨機(jī)跳入另一個(gè)頁(yè)面。d可以視為用戶(hù)無(wú)限點(diǎn)擊下去的概率，（1－d）則就是頁(yè)面本身所具有的網(wǎng)頁(yè)級(jí)別。

1.4、PageRank算法2（對(duì)算法1的修訂）

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中N是互聯(lián)網(wǎng)上所有網(wǎng)頁(yè)的數(shù)量

由此，所有頁(yè)面的網(wǎng)頁(yè)級(jí)別形成的一個(gè)概率分布，所有頁(yè)面的網(wǎng)頁(yè)級(jí)別之和是1。在算法1中，隨機(jī)沖浪訪(fǎng)問(wèn)某個(gè)頁(yè)面的概率由互聯(lián)網(wǎng)的總頁(yè)數(shù)決定，在算法2中，網(wǎng)頁(yè)級(jí)別是一個(gè)頁(yè)面被隨機(jī)訪(fǎng)問(wèn)的期望值。
　　以下講解，皆基于算法1，主要是計(jì)算簡(jiǎn)單，因?yàn)椴挥每紤]N的值。

1.5、PageRank的特性
　　所有頁(yè)面的網(wǎng)頁(yè)級(jí)別之和等于互聯(lián)網(wǎng)的總頁(yè)數(shù)。在網(wǎng)頁(yè)數(shù)比較少的情況下，網(wǎng)頁(yè)級(jí)別方程可以解出，而面對(duì)互聯(lián)網(wǎng)上成億的網(wǎng)頁(yè)，再解方程是不可能的。

此處設(shè)阻尼系數(shù)為0.5，雖然Lawrence Page 和 Sergey Brin在實(shí)際將其設(shè)為 0.85.

PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))                       
解得：                                   
PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615
有：
PR(A)+PR(B)+PR(C)=3

1.6、迭代計(jì)算pagerank
　　Google采用一種近似的迭代的方法計(jì)算網(wǎng)頁(yè)的網(wǎng)頁(yè)級(jí)別的，也就是先給每個(gè)網(wǎng)頁(yè)一個(gè)初始值，然后利用上面的公式，循環(huán)進(jìn)行有限次運(yùn)算得到近似的網(wǎng)頁(yè)級(jí)別。根據(jù)Lawrence Page 和 Sergey Brin公開(kāi)發(fā)表的文章，他們實(shí)際需要進(jìn)行100次迭代才能得到整個(gè)互聯(lián)網(wǎng)的滿(mǎn)意的網(wǎng)頁(yè)級(jí)別值，這兒的例子只用了10多次就可以了。在迭代的過(guò)程中，每個(gè)網(wǎng)頁(yè)的網(wǎng)頁(yè)級(jí)別的和是收斂于整個(gè)網(wǎng)絡(luò)的頁(yè)面數(shù)的。所以，每個(gè)頁(yè)面的平均網(wǎng)頁(yè)級(jí)別是1，實(shí)際上的值在（1－d）和(dN+(1-d))之間。

1.7、Google搜索引擎的網(wǎng)頁(yè)級(jí)別的實(shí)現(xiàn)
　　有三個(gè)因素決定的網(wǎng)頁(yè)的等級(jí)：網(wǎng)頁(yè)特定性因素、入鏈錨的文本、網(wǎng)頁(yè)級(jí)別。
　　網(wǎng)頁(yè)特定性因素包括網(wǎng)頁(yè)的內(nèi)容、標(biāo)題及URL等。
　　為提供檢索結(jié)果，Google根據(jù)網(wǎng)頁(yè)特定性因素和入鏈錨的文本計(jì)算出網(wǎng)頁(yè)的IR值，這個(gè)值被檢索項(xiàng)在頁(yè)面中的位置和重要性加權(quán)，以決定網(wǎng)頁(yè)和檢索請(qǐng)求相關(guān)性。IR值和網(wǎng)頁(yè)級(jí)別聯(lián)合標(biāo)志網(wǎng)頁(yè)的基本重要程度，這兩個(gè)值的聯(lián)合方式有多種，但明顯的是不能相加的。
　　由于網(wǎng)頁(yè)級(jí)別只對(duì)非特定的單個(gè)詞的檢索請(qǐng)求影響比較明顯，對(duì)于由多個(gè)檢索詞構(gòu)成的檢索請(qǐng)求，內(nèi)容相關(guān)性的分級(jí)標(biāo)準(zhǔn)的影響更大。

1.8、用Google工具條顯示當(dāng)前頁(yè)面的網(wǎng)頁(yè)級(jí)別
　　Google工具條是Google公司開(kāi)發(fā)的IE插件，需要從Google下載并安裝。注意，顯示網(wǎng)頁(yè)級(jí)別的功能是其高級(jí)功能，這時(shí)會(huì)自動(dòng)收集用戶(hù)的信息，并會(huì)自動(dòng)升級(jí)工具條。
　　這個(gè)工具條顯示的網(wǎng)頁(yè)級(jí)別分為0－10共11級(jí)，如果根據(jù)理論用(Nd+(1-d))測(cè)算，假定d=0.85,則推測(cè)實(shí)際網(wǎng)級(jí)別的對(duì)數(shù)即為顯示的級(jí)別，且對(duì)數(shù)的基數(shù)在6-7之間。

Google的目錄服務(wù)可以顯示網(wǎng)站的級(jí)別
　　此處級(jí)別分為7級(jí)。有人對(duì)兩種級(jí)別進(jìn)行了比較?！?/span>

1.9、入鏈對(duì)計(jì)算頁(yè)面級(jí)別的影響
　　入鏈總是能增加當(dāng)前頁(yè)面的級(jí)別，尤其當(dāng)前頁(yè)與其下級(jí)頁(yè)面構(gòu)成回路時(shí)，這種貢獻(xiàn)更大。如右圖例，設(shè)ABCD各 頁(yè)初始級(jí)別為1，阻尼系數(shù)為0.5，PR(X)/C(X)＝10。則易算出                         

PR(A) = 19/3 = 6.33                                      
PR(B) = 11/3 = 3.67                                        
PR(C) = 7/3 = 2.33
PR(D) = 5/3 = 1.67

如果A不在回路上，則只能得0.5*10=5的收益。
　　阻尼系數(shù)越大，頁(yè)面級(jí)別的收益越大，且整個(gè)回路上都能收到更大的收益（即入鏈?zhǔn)找娓芷骄胤植嫉礁鱾€(gè)回路頁(yè)面上。針對(duì)上例，將阻尼系數(shù)改為0.75，則有

PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63

除回路上各個(gè)頁(yè)面的級(jí)別值明顯增大外，PR(A)/PR(D)的值敢明顯減少了。
　　入鏈對(duì)整個(gè)回路上所有頁(yè)面的級(jí)別值的增加之和，可以由下面這個(gè)公式得出.

(d / (1-d)) × (PR(X) / C(X))

這個(gè)公式，可以由 簡(jiǎn)單推導(dǎo)出。
1.10、出鏈對(duì)計(jì)算頁(yè)面級(jí)別的影響
　　增加出鏈不會(huì)影響整個(gè)web的總級(jí)別，但一個(gè)站點(diǎn)失去的級(jí)別值等于鏈到的站點(diǎn)的增加值之和。對(duì)于兩個(gè)封閉的站點(diǎn)，從一個(gè)站點(diǎn)鏈上另一個(gè)站點(diǎn)時(shí)，增加的和減少的都是(d(/(1-d) × (PR(X) / C(X)).如果這兩個(gè)站點(diǎn)互相鏈接，則此值減少。用隨機(jī)沖浪模型可以解釋這種現(xiàn)象，就是出鏈的增加，減少了用戶(hù)訪(fǎng)問(wèn)站內(nèi)頁(yè)面的概率。舉例如圖，設(shè)阻尼系數(shù) 為0.75，則

PR(A) = 0.25 + 0.75 PR(B)
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.75 PR(D) + 0.375 PR(A)
PR(D) = 0.25 + 0.75 PR(C)
得：
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 35/23
PR(D) = 32/23
PR(A)+PR(B)=25/23
PR(C)+PR(D)=67/23
PR(A)+PR(B)+PR(C)+PR(D)=92/23=4

　　Page和Brin將這樣的鏈接稱(chēng)為懸擺鏈，它鏈到頁(yè)面沒(méi)有出鏈。懸擺鏈對(duì)頁(yè) 面的級(jí)別計(jì)算產(chǎn)生負(fù)面影響。如例，阻尼系數(shù)為0.75.  

PR(A) = 0.25 + 0.75 PR(B)                                         
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.375 PR(A)
得：
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 11/23
PR(A)+PR(B)+PR(C)=36/23<3

　　據(jù)Page和Brin，Google在索引頁(yè)面時(shí)，懸擺鏈的量很大，
主要是由于限制robot.txt的限制及索引了一些沒(méi)有鏈出的文件類(lèi)
型如PDF等。為消除這種負(fù)面影響，google在計(jì)算級(jí)別時(shí)，將此
類(lèi)鏈接從數(shù)據(jù)庫(kù)里去掉，在計(jì)算完畢后，再單獨(dú)計(jì)算懸擺鏈所鏈
到頁(yè)面。由此可見(jiàn)，PDF類(lèi)的文件還是可以放心地在網(wǎng)上發(fā)布的。





1.11、頁(yè)面數(shù)量的影響
　　先看例子。阻尼系數(shù)為0.75,PR(X)/C(X)=10,則

PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C))
PR(B) = PR(C) = 0.25 + 0.75 (PR(A) / 2)
得：                

PR(A) = 260/14
PR(B) = 101/14
PR(C) = 101/14
PR(A)+PR(B)+PR(C)=33;
增加頁(yè)面D；
PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C) + PR(D))
PR(B) = PR(C) = PR(D) = 0.25 + 0.75 (PR(A) / 3)
得
PR(A) = 266/14
PR(B) = 70/14
PR(C) = 70/14
PR(D) = 70/14
PR(A)+PR(B)+PR(C)+PR(D)=34

增加頁(yè)面后，所有頁(yè)面的級(jí)別值之和增加了1，A頁(yè)略有增加，而B、C則用大幅下降。
　　再看右邊的例子，假定同上。   

PR(A) = 0.25 + 0.75 (10 + PR(C))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
得：
PR(A) = 517/37 = 13.97
PR(B) = 397/37 = 10.73
PR(C) = 307/37 = 8.30

增加頁(yè)面D：
PR(A) = 0.25 + 0.75 (10 + PR(D))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
PR(D) = 0.25 + 0.75 × PR(C)
得：
PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63

增加頁(yè)面后，所有頁(yè)面級(jí)別增加了1，但每個(gè)頁(yè)面的級(jí)別值減少了，這是由于新加頁(yè)面分享了入鏈代來(lái)的值。從這個(gè)結(jié)果看，增加頁(yè)面減少了已有頁(yè)面的級(jí)別值，露了google算法青睞小站點(diǎn)的特點(diǎn)。當(dāng)然，大站點(diǎn)也會(huì)因內(nèi)容豐富而吸引其它 站點(diǎn)的出鏈而得以級(jí)別值增加。

1.12、針對(duì)搜索引擎優(yōu)化的級(jí)別分布
　　先看兩個(gè)列子，阻尼系數(shù)為0.5，PR(X)/C(X)=10;

BC之間無(wú)鏈接時(shí)： 

PR(A) = 0.5 + 0.5 (10 + PR(B) + PR (C))
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2)
得
PR(A) = 8
PR(B) = 2.5
PR(C) = 2.5
BC之間互相鏈接時(shí)：
PR(A) = 0.5 + 0.5 (10 + PR(B) / 2 + PR(C) / 2)
PR(B) = 0.5 + 0.5 (PR(A) / 2 + PR(C) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B) / 2)
得：
PR(A) = 7
PR(B) = 3
PR(C) = 3

當(dāng)BC 間互鏈時(shí)，雖然減少了A的級(jí)別，但BC都增加了。這符合優(yōu)化站點(diǎn)所有頁(yè)面而非只主頁(yè)的優(yōu)化思路，因?yàn)橹挥忻總€(gè)頁(yè)面的級(jí)別都提高了，當(dāng)有檢索詞命中這些頁(yè)面時(shí)，它們才能排在前面。這種優(yōu)化的方法也很明顯了，就是盡可能地在所有頁(yè)面間平均分布入鏈的貢獻(xiàn)，各低級(jí)頁(yè)面要增加互鏈。

只要不影響易用性，盡可能地將所有出鏈集中在一個(gè)或幾個(gè)低級(jí)頁(yè)面中，可以有效地降低出鏈對(duì)頁(yè)面級(jí)別計(jì)算的負(fù)面影響。看列子：阻尼系數(shù)為0.5， PR(X)/C(X)=10;

BCD都有出鏈時(shí)：

PR(A) = 0.5 + 0.5 (PR(B) / 2 + PR(C) / 2 + PR(D) / 2)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得：
PR(A) = 1
PR(B) = 2/3
PR(C) = 2/3
PR(D) = 2/3
出鏈集中于D時(shí)：
PR(A) = 0.5 + 0.5 (PR(B) + PR(C) + PR(D) / 4)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得：
PR(A) = 17/13
PR(B) = 28/39
PR(C) = 28/39
PR(D) = 28/39

從結(jié)果看，出鏈集中后，ABCD各頁(yè)面的級(jí)別都上升了。

1.13、影響頁(yè)面級(jí)別的其它因素
　　在Lawrence Page和Sergey Brin關(guān)于PageRank的論文發(fā)表以后，除了web的鏈接結(jié)構(gòu)以外，還有沒(méi)有別的因素被加到PageRank的算法當(dāng)中曾經(jīng)有過(guò)廣泛地討論。 Lawrence Page本人在PageRank的專(zhuān)利說(shuō)明中曾指出以下潛在的影響因素：鏈接的能見(jiàn)度，鏈接在文檔中的位置，web頁(yè)面間的距離，出鏈頁(yè)面的重要性，頁(yè)面的不過(guò)時(shí)。這此因素的增加，可以更好用隨機(jī)沖浪模型模擬人類(lèi)利用web的行為。
　　不管上述附加因素有沒(méi)有在實(shí)際計(jì)算PageRank時(shí)使用，如何實(shí)現(xiàn)這些附加因素仍要討論。
　　首先算法公式需要改進(jìn).

PR(A) = (1-d) + d (PR(T1)×L(T1,A) + ... + PR(Tn)×L(Tn,A))

此處，L(T1,A)是入鏈的評(píng)價(jià)值，由幾個(gè)因素構(gòu)成，只需要在迭代前計(jì)算一次，減少了對(duì)數(shù)據(jù)庫(kù)的查詢(xún)次數(shù)，雖然每次迭代的查詢(xún)結(jié)果會(huì)有不同。

Lawrence Page在PageRank的專(zhuān)利說(shuō)明中指出鏈接評(píng)價(jià)的兩個(gè)因素是鏈接的可見(jiàn)性和在文檔中的位置。鏈接評(píng)價(jià)取代了PR(A)/C(A)，指出了對(duì)一特定的頁(yè)面的鏈接，每個(gè)鏈接被點(diǎn)擊的概率是不同的。
　　此處，每一鏈接有兩個(gè)屬性值，X表示可見(jiàn)度，如果沒(méi)有被重點(diǎn)強(qiáng)調(diào)（如粗體、斜體等） 為1否則為2，Y表鏈接在文檔中的位置，如果在文檔下半部為1否則為3。則有    

X(A,B) × Y(A,B) = 1 × 3 = 3
X(A,C) × Y(A,C) = 1 × 1 = 1
X(B,A) × Y(B,A) = 2 × 3 = 6
X(B,C) × Y(B,C) = 2 × 1 = 2
X(C,A) × Y(C,A) = 2 × 3 = 6
X(C,B) × Y(C,B) = 2 × 1 = 2
易得：
Z(A) = X(A,B) × Y(A,B) + X(A,C) × Y(A,C) = 4
Z(B) = X(B,A) × Y(B,A) + X(B,C) × Y(B,C) = 8
Z(C) = X(C,A) × Y(C,A) + X(C,B) × Y(C,B) = 8
鏈接評(píng)價(jià)公式為：（頁(yè)面T1指向T2）
L(T1,T2) = X(T1,T2) × Y(T1,T2) / Z(T1)
有：
L(A,B) = 0.75
L(A,C) = 0.25
L(B,A) = 0.75
L(B,C) = 0.25
L(C,A) = 0.75
L(C,B) = 0.25
最后利用改進(jìn)的公式計(jì)算頁(yè)面級(jí)別：
PR(A) = 0.5 + 0.5 (0.75 PR(B) + 0.75 PR(C))
PR(B) = 0.5 + 0.5 (0.75 PR(A) + 0.25 PR(C))
PR(C) = 0.5 + 0.5 (0.25 PR(A) + 0.25 PR(B))
得：
PR(A) = 819/693
PR(B) = 721/693
PR(C) = 539/693

為了防止人為的級(jí)別優(yōu)化，頁(yè)面的距離被用來(lái)影響鏈接的評(píng)價(jià)。站內(nèi)鏈接的權(quán)重小于站間鏈接的權(quán)重。頁(yè)面的距離可能由頁(yè)面是否在一個(gè)站內(nèi)、一個(gè)服務(wù)器及物理距離等決定。
　　另一個(gè)影響頁(yè)面重要性的能參數(shù)，是頁(yè)面的不過(guò)時(shí)性（up-to-dateness），意指有越多的新建的頁(yè)面指向某一個(gè)頁(yè)面，則這個(gè)頁(yè)面內(nèi)容過(guò)時(shí)的可能性越小。
　　為增加這些因素的影響，要對(duì)公式進(jìn)行修訂如下：

L(Ti,A) = K(Ti,A) × K1(Ti) × ... × Km(Ti)

其中，K(Ti,A)表示鏈接可見(jiàn)度及位置的權(quán)重，Kn(Ti)是第n個(gè)因素對(duì)頁(yè)面Ti的影響?？戳凶樱捍颂帲瑥?/span>C引出的鏈接的重要性是其它 的4倍。

K(A) = 0.5
K(B) = 0.5
K(C) = 2
計(jì)算級(jí)別值：
PR(A) = 0.5 + 0.5 × 2 PR(C)
PR(B) = 0.5 + 0.5 × 0.5 × 0.5 PR(A)
PR(C) = 0.5 + 0.5 (0.5 PR(B) + 0.5 × 0.5 PR(A))
得：
PR(A) = 4/3
PR(B) = 2/3
PR(C) = 5/6

此時(shí)，所有頁(yè)面的級(jí)別之和不等于頁(yè)面數(shù)量。


1.14 PageRank 算法的改進(jìn)

 1. 主題敏感的PageRank（Topic-Sedsitive PageRank）
在這個(gè)算法中，我們需要預(yù)先計(jì)算離線(xiàn)時(shí)頁(yè)面的重要性的分?jǐn)?shù)；然后，我們?yōu)槊恳粋€(gè)頁(yè)面計(jì)算多種重要性分?jǐn)?shù)，即關(guān)于不同的主題來(lái)計(jì)算這個(gè)頁(yè)面的重要性分?jǐn)?shù)。在查詢(xún)的時(shí)候，把這些重要性分?jǐn)?shù)與根據(jù)被查詢(xún)的主題的重要性分?jǐn)?shù)綜合在一起，就形成一個(gè)復(fù)合的PageRank分?jǐn)?shù)。采用這種方法能形成更加精確的排序值，而不是原始普通的排序值。

2. 二次方程推斷法（Quadratic Extra polation）
這是一個(gè)可以加快PageRank的運(yùn)算速度的方法。它能通過(guò)周期性的削減當(dāng)前的矩陣乘冪迭代的非主要特征向量的方法，大大加快其收斂速度。使用這種方法計(jì)算PageRank值時(shí)，當(dāng)計(jì)算一個(gè)包含8000萬(wàn)個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)圖時(shí)，與采用原來(lái)的PageRank方法相比，計(jì)算速度可以提高20%-300%。

 3. 分塊矩陣排序算法（BlockRank Algo rithm）

該算法是PageRank算法的另一個(gè)加速算法，它首先把網(wǎng)絡(luò)根據(jù)領(lǐng)域劃分成不同的區(qū)域（塊），為每個(gè)區(qū)域計(jì)算它們的局部PageRank值；估計(jì)它們的相對(duì)的重要性（每個(gè)區(qū)域的BlockRank值）；用這個(gè)區(qū)域的Block-Rank.值來(lái)給每個(gè)區(qū)域的Block-Rank賦予一定的權(quán)重。然后再把這些加權(quán)的局部

的PageRank值近似地看作全局的PageRank向量，把這個(gè)向量作為標(biāo)準(zhǔn)的PageRank算法的開(kāi)始向量。這種方法可以減少計(jì)算的迭代次數(shù)，可以把更多的時(shí)間用于收斂速度慢的區(qū)域的計(jì)算，提高了局部PageRank計(jì)算的有效性。BlockRank算法可以采取并行或分布的形式來(lái)進(jìn)行計(jì)算，節(jié)約運(yùn)算的時(shí)間。此外，局部的PageRank計(jì)算結(jié)果在以后的計(jì)算中可以被再利用。