1. PageRank算法概述

PageRank，即網(wǎng)頁(yè)排名，又稱網(wǎng)頁(yè)級(jí)別、Google左側(cè)排名或佩奇排名。

在谷歌主導(dǎo)互聯(lián)網(wǎng)搜索之前， 多數(shù)搜索引擎采用的排序方法， 是以被搜索詞語(yǔ)在網(wǎng)頁(yè)中的出現(xiàn)次數(shù)來(lái)決定排序——出現(xiàn)次數(shù)越多的網(wǎng)頁(yè)排在越前面。 這個(gè)判據(jù)不能說(shuō)毫無(wú)道理， 因?yàn)橛脩羲阉饕粋€(gè)詞語(yǔ)， 通常表明對(duì)該詞語(yǔ)感興趣。 既然如此， 那該詞語(yǔ)在網(wǎng)頁(yè)中的出現(xiàn)次數(shù)越多， 就越有可能表示該網(wǎng)頁(yè)是用戶所需要的。

可惜的是，這個(gè)貌似合理的方法實(shí)際上卻行不大通。 因?yàn)榘凑者@種方法， 任何一個(gè)象祥林嫂一樣翻來(lái)復(fù)去倒騰某些關(guān)鍵詞的網(wǎng)頁(yè)， 無(wú)論水平多爛， 一旦被搜索到， 都立刻會(huì) “金榜題名”， 這簡(jiǎn)直就是廣告及垃圾網(wǎng)頁(yè)制造者的天堂。

是Google創(chuàng)始人拉里·佩奇和謝爾蓋·布林于1997年構(gòu)建早期的搜索系統(tǒng)原型時(shí)提出的鏈接分析算法，自從Google在商業(yè)上獲得空前的成功后，該算法也成為其他搜索引擎和學(xué)術(shù)界十分關(guān)注的計(jì)算模型。目前很多重要的鏈接分析算法都是在PageRank算法基礎(chǔ)上衍生出來(lái)的。

PageRank是Google用于用來(lái)標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的一種方法，是Google用來(lái)衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如Title標(biāo)識(shí)和Keywords標(biāo)識(shí)等所有其它因素之后，Google通過(guò)PageRank來(lái)調(diào)整結(jié)果，使那些更具“等級(jí)/重要性”的網(wǎng)頁(yè)在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。其級(jí)別從0到10級(jí)，10級(jí)為滿分。PR值越高說(shuō)明該網(wǎng)頁(yè)越受歡迎（越重要）。

例如：一個(gè)PR值為1的網(wǎng)站表明這個(gè)網(wǎng)站不太具有流行度，而PR值為7到10則表明這個(gè)網(wǎng)站非常受歡迎（或者說(shuō)極其重要）。一般PR值達(dá)到4，就算是一個(gè)不錯(cuò)的網(wǎng)站了。Google把自己的網(wǎng)站的PR值定到10，這說(shuō)明Google這個(gè)網(wǎng)站是非常受歡迎的，也可以說(shuō)這個(gè)網(wǎng)站非常重要。

2. 從入鏈數(shù)量到 PageRank

在PageRank提出之前，已經(jīng)有研究者提出利用網(wǎng)頁(yè)的入鏈數(shù)量來(lái)進(jìn)行鏈接分析計(jì)算，這種入鏈方法假設(shè)一個(gè)網(wǎng)頁(yè)的入鏈越多，則該網(wǎng)頁(yè)越重要。早期的很多搜索引擎也采納了入鏈數(shù)量作為鏈接分析方法，對(duì)于搜索引擎效果提升也有較明顯的效果。 PageRank除了考慮到入鏈數(shù)量的影響，還參考了網(wǎng)頁(yè)質(zhì)量因素，兩者相結(jié)合獲得了更好的網(wǎng)頁(yè)重要性評(píng)價(jià)標(biāo)準(zhǔn)。

對(duì)于某個(gè)互聯(lián)網(wǎng)網(wǎng)頁(yè)A來(lái)說(shuō)，該網(wǎng)頁(yè)P(yáng)ageRank的計(jì)算基于以下兩個(gè)基本假設(shè)：

數(shù)量假設(shè)：在Web圖模型中，如果一個(gè)頁(yè)面節(jié)點(diǎn)接收到的其他網(wǎng)頁(yè)指向的入鏈數(shù)量越多，那么這個(gè)頁(yè)面越重要。

質(zhì)量假設(shè)：指向頁(yè)面A的入鏈質(zhì)量不同，質(zhì)量高的頁(yè)面會(huì)通過(guò)鏈接向其他頁(yè)面?zhèn)鬟f更多的權(quán)重。所以越是質(zhì)量高的頁(yè)面指向頁(yè)面A，則頁(yè)面A越重要。

利用以上兩個(gè)假設(shè)，PageRank算法剛開(kāi)始賦予每個(gè)網(wǎng)頁(yè)相同的重要性得分，通過(guò)迭代遞歸計(jì)算來(lái)更新每個(gè)頁(yè)面節(jié)點(diǎn)的PageRank得分，直到得分穩(wěn)定為止。 PageRank計(jì)算得出的結(jié)果是網(wǎng)頁(yè)的重要性評(píng)價(jià)，這和用戶輸入的查詢是沒(méi)有任何關(guān)系的，即算法是主題無(wú)關(guān)的。假設(shè)有一個(gè)搜索引擎，其相似度計(jì)算函數(shù)不考慮內(nèi)容相似因素，完全采用PageRank來(lái)進(jìn)行排序，那么這個(gè)搜索引擎的表現(xiàn)是什么樣子的呢？這個(gè)搜索引擎對(duì)于任意不同的查詢請(qǐng)求，返回的結(jié)果都是相同的，即返回PageRank值最高的頁(yè)面。

3. PageRank算法原理

PageRank的計(jì)算充分利用了兩個(gè)假設(shè)：數(shù)量假設(shè)和質(zhì)量假設(shè)。步驟如下：

1）在初始階段：網(wǎng)頁(yè)通過(guò)鏈接關(guān)系構(gòu)建起Web圖，每個(gè)頁(yè)面設(shè)置相同的PageRank值，通過(guò)若干輪的計(jì)算，會(huì)得到每個(gè)頁(yè)面所獲得的最終PageRank值。隨著每一輪的計(jì)算進(jìn)行，網(wǎng)頁(yè)當(dāng)前的PageRank值會(huì)不斷得到更新。

2）在一輪中更新頁(yè)面PageRank得分的計(jì)算方法：在一輪更新頁(yè)面PageRank得分的計(jì)算中，每個(gè)頁(yè)面將其當(dāng)前的PageRank值平均分配到本頁(yè)面包含的出鏈上，這樣每個(gè)鏈接即獲得了相應(yīng)的權(quán)值。而每個(gè)頁(yè)面將所有指向本頁(yè)面的入鏈所傳入的權(quán)值求和，即可得到新的PageRank得分。當(dāng)每個(gè)頁(yè)面都獲得了更新后的PageRank值，就完成了一輪PageRank計(jì)算。

3.2 基本思想：

如果網(wǎng)頁(yè)T存在一個(gè)指向網(wǎng)頁(yè)A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個(gè)重要性得分值為：PR（T）/L(T)

其中PR（T）為T的PageRank值，L(T)為T的出鏈數(shù)

則A的PageRank值為一系列類似于T的頁(yè)面重要性得分值的累加。

即一個(gè)頁(yè)面的得票數(shù)由所有鏈向它的頁(yè)面的重要性來(lái)決定，到一個(gè)頁(yè)面的超鏈接相當(dāng)于對(duì)該頁(yè)投一票。一個(gè)頁(yè)面的PageRank是由所有鏈向它的頁(yè)面（鏈入頁(yè)面）的重要性經(jīng)過(guò)遞歸算法得到的。一個(gè)有較多鏈入的頁(yè)面會(huì)有較高的等級(jí)，相反如果一個(gè)頁(yè)面沒(méi)有任何鏈入頁(yè)面，那么它沒(méi)有等級(jí)。

3.3 PageRank簡(jiǎn)單計(jì)算：

假設(shè)一個(gè)由只有4個(gè)頁(yè)面組成的集合：A，B，C和D。如果所有頁(yè)面都鏈向A，那么A的PR（PageRank）值將是B，C及D的和。

繼續(xù)假設(shè)B也有鏈接到C，并且D也有鏈接到包括A的3個(gè)頁(yè)面。一個(gè)頁(yè)面不能投票2次。所以B給每個(gè)頁(yè)面半票。以同樣的邏輯，D投出的票只有三分之一算到了A的PageRank上。

換句話說(shuō)，根據(jù)鏈出總數(shù)平分一個(gè)頁(yè)面的PR值。

例子：

如圖1 所示的例子來(lái)說(shuō)明PageRank的具體計(jì)算過(guò)程。