Pagerank

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

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

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

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

## 概述

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 年初，Google 公司為網頁連結推出一項新屬性 nofollow，使得網站管理員和部落格作者可以建立一些不計票的連結，也就是說這些連結不算作「投票」，從而實現抵制垃圾投票的目的。

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

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 的連結規範中已清楚地說明，哪些是屬於違反規範的行為。

## 從 Google 工具列中移除

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

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

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

2016 年 4 月 15 日，Google 公司停止向公眾開放 PageRank 資料。就在幾個月前，Google 也聲明將會將 PageRank 評分自 Google 工具列中移除。 但是，今後 Google 公司在對其搜尋引擎的搜尋結果進行排名時，仍然會使用 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