搜尋引擎中最早網頁搜尋結果排序效果比較優的算法就是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是從事搜尋領域人士必須要了解的算法之一。
本文由 @King James 原創釋出于人人都是産品經理。未經許可，禁止轉載。
題圖來自 Unsplash，基于 CC0 協定
該文觀點僅代表作者本人，人人都是産品經理平台僅提供資訊存儲空間服務。