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

一、基本假設

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

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

數(shù)量假設：當一個網(wǎng)頁被其他網(wǎng)頁鏈接的數(shù)量越多，入鏈數(shù)越大，則該網(wǎng)頁越重要。

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

• 質(zhì)量假設：被高質(zhì)量的網(wǎng)頁鏈接時，說明被鏈接的網(wǎng)頁質(zhì)量也很高，權(quán)威性也很強。

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

二、Page Rank基本算法

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

每個節(jié)點的Page Rank值（以下簡稱PR值）表示該節(jié)點的權(quán)威性。我們核心是構(gòu)建一個用戶在圖網(wǎng)絡中的游走模型，基于游走模型來進行PR值的更新迭代。

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

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

三、具體案例

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

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

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

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

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

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

四、Page Rank優(yōu)化算法

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

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

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

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

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