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

一、基本假設(shè)

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

于是我們設(shè)定以下兩大假設(shè)。

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

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

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

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

二、Page Rank基本算法

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

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

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

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

三、具體案例

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

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

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

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

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

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

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

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

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

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

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

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