PageRank

Google的工具列標示出的中文維基百科首頁的PageRank

PageRank又稱網頁排名、谷歌左側排名、PR，是Google公司所使用的對其搜尋引擎搜尋結果中的網頁進行排名的一種演算法。

PageRank本質上是一種以網頁之間的超連結個數和質素作為主要因素粗略地分析網頁的重要性的演算法。其基本假設是：更重要的頁面往往更多地被其他頁面參照（或稱其他頁面中會更多地加入通向該頁面的超連結）。 其將從A頁面到B頁面的連結解釋為「A頁面給B頁面投票」，並根據投票來源（甚至來源的來源，即連結到A頁面的頁面）和投票對象的等級來決定被投票頁面的等級。簡單的說，一個高等級的頁面可以提升其他低等級的頁面。

該演算法以谷歌公司創始人之一的賴利·佩吉的名字來命名。谷歌搜尋引擎用它來分析網頁的相關性和重要性，在搜尋引擎最佳化中經常被用來作為評估網頁最佳化的成效因素之一。

目前，PageRank演算法不再是谷歌公司用來給網頁進行排名的唯一演算法，但它是最早的，也是最著名的演算法。

概述

PageRank的卡通概念圖，圖中笑臉的大小與指向該笑臉的其他笑臉的數目成正比.

PageRank是一種連結分析演算法，它通過對超連結集合中的元素用數字進行權重賦值，實現「衡量集合範圍內某一元素的相關重要性」的目的。該演算法可以應用於任何含有元素之間相互參照的情況的集合實體。我們將其中任意元素E的權重數值稱為「E的PageRank」（The PageRank of E），用符號表示為 $PR(E)$。其他的因素，類似「作者排名（Author Rank）」同樣可以影響到該元素的權重值。

PageRank的結果來源於一種基於圖論的數學演算法。它將萬維網上所有的網頁視作節點（node），而將超連結視作邊（edge），並且考慮到了一些權威的網站，類似CNN。每個節點的權重值表示對應的頁面的重要度。通向該網頁的超連結稱做「對該網頁的投票（a vote of support）」。每個網頁的權重值大小被遞歸地定義，依託於所有連結該頁面的頁面的權重值。例如，一個被很多頁面的連結的頁面將會擁有較高的權重值（high PageRank）。

大量關於PageRank的學術論文在Page和Brin的原版論文前就已有之。在實際情況中，PageRank很容易被利用。相關的研究往往會關注那些因受到影響而出現錯誤的PageRank結果，以找到一種有效地避免其被錯誤地影響的方法（如忽略部分錯誤的連結）。 2005年初，谷歌公司為網頁連結推出一項新屬性nofollow，使得網站管理員和網誌作者可以建立一些不計票的連結，也就是說這些連結不算作「投票」，從而實現抵制垃圾投票的目的。

Google工具列上的PageRank指標從0到10。它似乎是一個對數標度演算法，細節未知。雖然PageRank是谷歌的商標，其技術亦已經申請專利，但是專利權屬於史丹福大學，而非谷歌公司。

PageRank演算法中的點擊演算法是由喬恩·克萊因伯格(Jon Kleinberg)提出的。而其他的基於連結的網頁排名演算法，則包括喬恩·克萊因伯格發明的HITS演算法，IBM CLEVER Project，TrustRank演算法以及hummingbird演算法等等。

演算法

PageRank演算法通過輸出概率分佈來體現某人隨機地點擊某個連結的概率。PageRank值（PR）可以在任何規模的檔案（document）集合中計算得出，而每個連結都指向該集合中的某個特定檔案。相關研究論文指出，在初次計算前，總概率將被均分到每個檔案上，使得集合中的每個檔案被訪問的概率都是相同的。接下來在重複多次的計算（又稱為「迭代」）中，演算法將根據集合的實際情況不斷調整PR值，使得其越來越接近最真實的理論值。

最終的概率將通過一個在0與1之間的數值體現。概率為0.5通常意味着該事件有50%的可能性發生。因此，「PR=0.5」代表「有50%的可能性，某人點擊了一個隨機的連結並訪問了該連結指向的檔案」。

簡化版本

假設一個由4個網頁組成的集合：A，B，C和D。同一頁面中多個指向相同的連結視為同一個連結，並且每個頁面初始的PageRank值相同，最初的演算法將每個網頁的初始值設定為1。但是在後來的版本以及下面的範例中，為了滿足概率值位於0到1之間的需要，我們假設這個值是0.25。

在每次迭代中，給定頁面的PR值（PageRank值）將均分到該頁面所連結的頁面上。

如果所有頁面都只連結至A，那麼A的PR值將是B，C及D的PR值之和，即：

$PR(A)=PR(B)+PR(C)+PR(D)$

重新假設B連結到A和C，C連結到A，並且D連結到A,B,C。最初一個頁面總共只有一票。所以B給A ,C每個頁面半票。以此類推，D投出的票只有三分之一加到了A的PR值上：

$PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}$

換句話說，演算法將根據每個頁面連出總數 $L(x)$平分該頁面的PR值，並將其加到其所指向的頁面：

$PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}$

最後，所有這些PR值被換算成百分比形式再乘上一個修正係數 $d$。由於「沒有向外部連結接的網頁」傳遞出去的PR值會是0，而這會遞歸地導致指向它的頁面的PR值的計算結果同樣為零，所以賦給每個頁面一個最小值$(1-d)/N$：

$PR(A)=\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right)d+{\frac {1-d}{N}}$

• 需要注意的是，在Sergey Brin和Lawrence Page的1998年原版論文中給每一個頁面設定的最小值是$1-d$，而不是這裏的$(1-d)/N$，這將導致集合中所有網頁的PR值之和為N（N為集合中網頁的數目）而非所期待的1。

因此，一個頁面的PR值直接取決於指向它的的頁面。如果在最初給每個網頁一個隨機且非零的PR值，經過重複計算，這些頁面的PR值會趨向於某個定值，也就是處於收斂的狀態，即最終結果。這就是搜尋引擎使用該演算法的原因。

完整版本

這個方程式引入了隨機瀏覽者（random surfer）的概念，即假設某人在瀏覽器中隨機打開某些頁面並點擊了某些連結。為了便於理解，這裏假設上網者不斷點擊網頁上的連結直到進入一個沒有外部連結的網頁，此時他會隨機瀏覽其他的網頁（可以與之前的網頁無關）。

為了處理那些「沒有外部連結的頁面」（這些頁面就像「黑洞」一樣吞噬掉用戶繼續向下瀏覽的概率）所帶來的問題，我們假設：這類頁面連結到集合中所有的網頁（不管它們是否相關），使得這類網頁的PR值將被所有網頁均分。對於這種殘差概率（residual probability），我們引入阻尼係數 $d$（damping factor），並聲明 $d=0.85$，其意義是：任意時刻，用戶訪問到某頁面後繼續訪問下一個頁面的概率，相對應的 $1-d=0.15$ 則是用戶停止點擊，隨機瀏覽新網頁的概率。$d$ 的大小由一般上網者使用瀏覽器書籤功能的頻率的平均值估算得到。

所以，對於某個頁面i，其對應PR值大小的計算公式如下：

${\rm {PR}}(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {{\rm {PR}}(p_{j})}{L(p_{j})}}$

• 這裏，$p_{1},p_{2},...,p_{N}$是目標頁面$p_{i}$，$M(p_{i})$是鏈入$p_{i}$頁面的集合，$L(p_{j})$是頁面$p_{j}$鏈出頁面的數量，而$N$是集合中所有頁面的數量。

集合中所有頁面的PR值可以由一個特殊的鄰接矩陣的特徵向量表示。這個特徵向量R為：

$\mathbf {R} ={\begin{bmatrix}{\rm {PR}}(p_{1})\\{\rm {PR}}(p_{2})\\\vdots \\{\rm {PR}}(p_{N})\end{bmatrix}}$

同時，R也是下面的方程組的解：

$\mathbf {R} ={\begin{bmatrix}{(1-d)/N}\\{(1-d)/N}\\\vdots \\{(1-d)/N}\end{bmatrix}}+d{\begin{bmatrix}\ell (p_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&&&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R}$

• 這裏的鄰接函數（adjacency function） $\ell (p_{i},p_{j})$ 代表「從頁面j指向頁面i的連結數」與「頁面j中含有的外部連結總數」的比值

如果$p_{j}$不鏈向$p_{i}$，則前面提到的「從頁面j指向頁面i的連結數」為零。將情況一般化：對於特定的j，應有：

$\sum _{i=1}^{N}\ell (p_{i},p_{j})=1,$

由於上述修改後的鄰接矩陣的巨大的eigengap值，幾次迭代後即可在極高的精確度下估計PageRank特徵向量R的值。

缺陷

PageRank演算法的主要缺點在於舊的頁面的排名往往會比新頁面高。因為即使是質素很高的新頁面也往往不會有很多外部連結，除非它是某個已經存在站點的子站點。這也是PageRank需要多項演算法結合以保證其結果的準確性的原因。例如，PageRank似乎偏好於維基百科頁面，在條目名稱的搜尋結果中，維基百科頁面經常在大多數頁面甚至所有頁面之前，此現象的原因則是維基百科內聯網頁中存在大量的內部連結，同時亦有很多站點鏈入維基百科。

Google經常處罰惡意提高網頁PageRank的行為。至於其如何區分正常的連結和不正常的連結，這仍然是商業機密。但是在Google的連結規範中已清楚地說明，哪些是屬於違反規範的行為。

從谷歌工具列中移除

2009年10月14日，Google員工蘇珊·莫斯科（Susan Moskwa）確認該公司已將PageRank從其網站管理員工具中移除。她表示：「我們長久以來一直在告誡人們不應該過分注重PageRank；很多網站站長似乎認為PageRank是他們需要時刻關注的最重要的指標，而這幾乎是錯誤的。」然而在蘇珊確認後兩天，PageRank又在谷歌工具欄（Google Toolbar）上重新顯示，但其指示器（indicator）在谷歌公司自家的Chrome瀏覽器上已不可用。

同時，公眾可見的PageRank的數據更新周期也越來越長，它的最後一次更新是2013年11月份。

2014年10月7日，谷歌員工John Mueller表示 ：「我們可能不會繼續更新PageRank，至少工具列上的PageRank是這樣。」

2016年4月15日，谷歌公司停止向公眾開放PageRank數據。就在幾個月前，谷歌也聲明將會將PageRank評分自谷歌工具列中移除。 但是，今後谷歌公司在對其搜尋引擎的搜尋結果進行排名時，仍然會使用PageRank中的數據。

外部連結

• Our Search: Google Technology（頁面存檔備份，存於互聯網檔案館） by Google （英文）
• The PageRank Citation Ranking: Bringing Order to the Web by Larry Page et al. （英文）
• The PageRank Result （英文）

參見

• Google
• Google轟炸
• SimRank