PageRank

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

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

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

該算法以谷歌公司創始人之一的拉里·佩奇的名字來命名。^[2]谷歌搜索引擎用它來分析網頁的相關性和重要性，在搜索引擎優化中經常被用來作為評估網頁優化的成效因素之一。

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

概述

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

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

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

大量關於PageRank的學術論文在Page和Brin的原版論文前就已有之。^[5]在實際情況中，PageRank很容易被利用。相關的研究往往會關注那些因受到影響而出現錯誤的PageRank結果，以找到一種有效地避免其被錯誤地影響的方法（如忽略部分錯誤的鏈接）。^[6] 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值）將均分到該頁面所鏈接的^{[註 1]}頁面上。

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

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

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

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

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

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

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

${\displaystyle 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年原版論文中給每一個頁面設定的最小值是${\displaystyle 1-d}$，而不是這裡的${\displaystyle (1-d)/N}$，這將導致集合中所有網頁的PR值之和為N（N為集合中網頁的數目）而非所期待的1。

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

完整版本

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

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

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

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

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

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

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

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

${\displaystyle \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） ${\displaystyle \ell (p_{i},p_{j})}$ 代表「從頁面j指向頁面i的鏈接數」與「頁面j中含有的外部連結總數」的比值

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

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

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

缺陷

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

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

從谷歌工具欄中移除

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

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

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

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

腳註

1. 此處以及下文中的鏈接均為單向鏈接，即A->B不等價於B->A
2. 有關該係數的明確定義請見下面的#完整版本

參考文獻

1. Facts about Google and Competition. [12 July 2014]. （原始內容存檔於2011-11-04）.
2. Google Press Center: Fun Facts. www.google.com. [2018-12-09]. （原始內容存檔於2001-07-15）.
3. Sullivan, Danny. What Is Google PageRank? A Guide For Searchers & Webmasters. Search Engine Land. [2018-12-09]. （原始內容存檔於2016-07-03）.
4. Cutts, Matt. Algorithms Rank Relevant Results Higher. www.google.com. [19 October 2015]. （原始內容存檔於2013-07-02）.
5. Brin, S.; Page, L. The anatomy of a large-scale hypertextual Web search engine (PDF). Computer Networks and ISDN Systems. 1998, 30: 107–117 [2018-12-10]. ISSN 0169-7552. doi:10.1016/S0169-7552(98)00110-X. （原始內容存檔 (PDF)於2015-09-27）.
6. Gyöngyi, Zoltán; Berkhin, Pavel; Garcia-Molina, Hector; Pedersen, Jan, Link spam detection based on mass estimation, Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB '06, Seoul, Korea) (PDF): 439–450, 2006 [2018-12-10], （原始內容存檔 (PDF)於2014-12-03）.
7. Web Structure Age and Page Quality. (PDF). [2002-05]. （原始內容 (PDF)存檔於2021-07-20）.
8. 链接方案 - Search Console帮助. support.google.com. [2016-12-16]. （原始內容存檔於2016-12-21）.
9. Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]. （原始內容存檔於2009-10-17）.
10. Google Toolbar PageRank Finally & Officially Dead?. Search Engine Land. 2014-10-07 [2016-12-16]. （原始內容存檔於2016-12-20） （美國英語）.
11. Schwartz, Barry. Google Toolbar PageRank officially goes dark. Search Engine Land. [2018-12-10]. （原始內容存檔於2016-04-21）.
12. Southern, Matt. Google PageRank Officially Shuts its Doors to the Public. Search Engine Journal. [2018-12-10]. （原始內容存檔於2017-04-13）.

外部連結

• 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
• Google轟炸
• SimRank