搜索引擎中最早網頁搜索結果排序效果比較優的算法就是Google創始人提出的Page Rank算法，作為搜索領域的從業者必須要了解該經典算法的思想。本文結合實際案例一篇講懂Page Rank算法的基本思想，同時還為大家介紹后續優化后的Page Rank算法。

一、基本假設

在正式介紹Page Rank算法前我們先通過實際生活中的一個案例入手。日常我們寫論文時經常會引用別人的論文，某個行業里的經典論文會被大量的論文所引用。如果該論文恰好還被另外一篇經典論文所引用的話，則更加能夠凸顯出該篇論文的重要性和權威性，其實網頁的重要性和權威性也是如此。

于是我們設定以下兩大假設。

數量假設：當一個網頁被其他網頁鏈接的數量越多，入鏈數越大，則該網頁越重要。

如上圖所示，網站“WWW1”被眾多網站引用，形成了鏈接，則說明網站“WWW1”很重要。

• 質量假設：被高質量的網頁鏈接時，說明被鏈接的網頁質量也很高，權威性也很強。

如上圖所示，網站“WWW8”被高質量網站“WWW1”引用，形成了鏈接，說明網站“WWW8”同樣也很權威。PageRank算法的整體思想都是建立在上述假設上的。

二、Page Rank基本算法

基于以上兩大假設，我們展開介紹Page Rank算法。首先我們將互聯網想象為一個圖網絡，網絡的每一個節點（Node）就是一個個獨立的網頁，如果兩個網頁之間存在超鏈接的關系，則它們兩個之間存在一條有方向的邊（Edge），每個節點向外鏈接的節點數被稱為該節點的出度。

每個節點的Page Rank值（以下簡稱PR值）表示該節點的權威性。我們核心是構建一個用戶在圖網絡中的游走模型，基于游走模型來進行PR值的更新迭代。

上面即為Page Rank算法的基本定義，首先節點 ν_1 的PR值是由鏈接到該節點的其他節點PR值決定的，假設鏈接節點是 ν_2、ν_3 。鏈接的其他節點越多則該節點的PR值越大，所以算法迭代使用累加 ∑ 。需要將節點 ν_2、ν_3 的PR值進行累加，此迭代思路對應著上述的“數量假設”。

鏈接的其他節點PR值越大，則該節點的PR值也越大，對應著上述的“質量假設”。同時 ν_2、ν_3 節點還鏈接其他節點，用戶通過節點 ν_2、ν_3 跳轉到節點 ν_1 的概率為 1/O(ν_j ) ， O(ν_j ) 為節點 ν_j 的出度。節點 ν_2、ν_3 的PR值分別乘以 1/O(ν_2 )和1/O(ν_3 ) ，再進行累加即為節點 ν_1 的PR值。我們通過該方式不斷迭代更新節點的PR值，直到最終整個網絡里所有節點的PR值滿足收斂條件。

三、具體案例

下面我們通過一個例子來詳細介紹Page Rank算法的迭代過程。

初始時4個節點的PR值均為1/4。經過第一次迭代，我們得到了 R_1 =[3/8,5/24,5/24,5/24]^T 。我們可以將上述計算過程變成一個矩陣計算，通過矩陣化的表達，可以快速的計算得到PR值。

首先我們基于各個節點的出度構建一個轉移概率矩陣 M ，節點A的出度為3，鏈接了B、C、D三個節點，我們認為節點A轉移到B、C、D節點的概率均為1/3，以此類推我們可以得到一個轉移概率矩陣 M 。那么PR的迭代公式就變為： M*R_t=R_(t+1) 。

如上所示 M*R_1=R_2 ，和我們最上方計算的結果完全一致。但是上述Page Rank基本算法應用時會存在以下兩大問題：

問題一：很多網站并沒有和其他網站建立任何的鏈接，出度為0。這類網站的出現會導致按照上述算法進行 R_i 迭代，最終所有節點的PR值歸于零。

問題二：用戶打開某一個網站后，即使該網站鏈接了其他網站，但是用戶還是可能會隨機打開其他網站，所以沒有鏈接的其他網站轉移概率不應該是0，系統可以設置一個隨機概率。

四、Page Rank優化算法

基于Page Rank基本算法存在的兩大問題上，科學家們又對Page Rank算法進行了優化，優化后的Page Rank算法可以適用于所有的網絡結構，更加貼近于實際用戶瀏覽行為。優化后的算法PR值更新迭代如下：

R_(t+1)=d*M*R_t+(1-d)*E/N

全新迭代公式的業務理解是：用戶在瀏覽網頁時有兩種情況，第一種情況是以概率 d(0≤d≤1) 完全按照原本的轉移概率矩陣進行游走，第二種情況是以概率（1- d ）隨機訪問任何其他的節點，每個節點的鏈接概率都是1/N， E 是元素1填滿的N*N矩陣。

d 又被成為阻尼因子， d 的取值一般由經驗決定，正常在0.8-0.9之間。當 d 接近1時，用戶隨機游走主要依照轉移概率矩陣 M 進行；當 d 接近0時，用戶隨機游走主要以等概率隨機訪問各個結點。

雖然目前搜索引擎的排序算法已經優化迭代了很多版本，但是Page Rank算法的核心思想仍然在被使用，也應用到了其他領域。Page Rank是從事搜索領域人士必須要了解的算法之一。