Google的網頁排名演算法

Google並不是第一家搜索引擎公司，但後來卻成為龍頭行業，這其中PageRank演算法發揮著重要的作用。PageRank是Google創始人之一Larry Page發明的，今天我們就來一起瞻仰下大神的創作。

互聯網上的每一個網頁都可以看作一個頂點，每一個頂點都有出度和入度。出度是指從這個網頁能鏈接到的其他網頁的數目，入度是指能鏈接到這個網頁的其他網頁的數目。

這樣整個互聯網中的所有網頁的鏈接關係可以看成具有大量網頁結點的有向圖。一個網頁很重要最直觀的感受就是有許多的網頁鏈接到它，即它的入度大，並且重要性越高的網頁鏈接它更能說明它越重要。

基於以上思想，我們首先量化網頁的重要性，用PR值表示重要性，一個網頁的PR值越大表明這個網頁越重要。

PageRank的簡化模型

一個網頁的PR值在一定程序上取決於它的入度，也和鏈接到它的網頁本身的PR值有關，基於這個思想，計算任意一個網頁的PR值的公式如下。

其中Bu是所有鏈接到u網頁的網頁集合，網頁v屬於集合Bu，L(v)是網頁v的出度。下面我們就用下圖的網頁鏈接關係舉例。

假定A、B、C、D網頁的初始PR值都為0.25，根據上面的計算公式，我們有如下的計算過程。

經過多次的迭代計算後，PR值逐漸穩定，即可認為PR值收斂。從計算結果看出，B、D的PR值較高，這表明B、D的重要程度高，這也符合我們對圖的直觀感受。

但真實的網頁鏈接關係複雜，這種簡化的模型會面臨以下兩個問題。

1.排名泄漏

如果有向圖中有一個頂點的出度為0，即這個網頁沒有鏈接到其他的網頁，則會出現排名泄漏問題。以下圖為例，A頂點的出度為0。

以此圖的迭代計算過程如下。

出現這種問題的原因可以理解為A網頁對整個網頁沒有PR值的貢獻，因為它的出度為0，相反它還吸收其它網頁對它PR值的貢獻，導致整個網頁的PR值越來越小。

2.排名下沉

如果有向圖中有一個頂點的入度為0，即沒有其他網頁鏈接到這個網頁，則會出現排名下沉問題。以下圖為例，A頂點的入度為0。

因為A的入度為0，則在第一次迭代的時候A的PR值就為0，以後都為0。

為了解決簡化模型出現的以上兩個問題，PageRank的隨機瀏覽模型應運而生。

PageRank的隨機瀏覽模型

隨機瀏覽模型是符合用戶上網行為的一種模型。用戶隨機打開一個網頁後，要麼點擊這個網頁上的鏈接繼續網頁的瀏覽，要麼隨機轉到另外的一個網頁重新開始新一輪的瀏覽。

為此隨機瀏覽模型引入了一個阻尼係數d來表示用戶點擊此網頁上的鏈接繼續瀏覽的概率，則1-d就是用戶重新進行新一輪的瀏覽的概率。引入阻尼係數d的計算公式如下。

其中N為整個網頁的數目。

引入阻尼係數的效果為：在原有的有向圖中添加了一個全鏈接的瀏覽關係，這樣就完全解決了簡化模型中出現的排名泄漏和排名下沉的問題。如下圖所示。

其中虛線就是隨機瀏覽模型添加的全鏈接關係。

以上就是Google開創的PageRank演算法，是不是覺得原理很簡單，但就是這樣一個原理簡單的演算法使Google成為搜索領域的霸主。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！