google并不是第一家搜索引擎公司，但后來卻成為龍頭行業(yè)，這其中pagerank算法發(fā)揮著重要的作用。pagerank是google創(chuàng)始人之一larry page發(fā)明的，今天我們就來一起瞻仰下大神的創(chuàng)作。
互聯網上的每一個網頁都可以看作一個頂點，每一個頂點都有出度和入度。出度是指從這個網頁能鏈接到的其他網頁的數目，入度是指能鏈接到這個網頁的其他網頁的數目。
這樣整個互聯網中的所有網頁的鏈接關系可以看成具有大量網頁結點的有向圖。一個網頁很重要最直觀的感受就是有許多的網頁鏈接到它，即它的入度大，并且重要性越高的網頁鏈接它更能說明它越重要。
基于以上思想，我們首先量化網頁的重要性，用pr值表示重要性，一個網頁的pr值越大表明這個網頁越重要。
pagerank的簡化模型
一個網頁的pr值在一定程序上取決于它的入度，也和鏈接到它的網頁本身的pr值有關，基于這個思想，計算任意一個網頁的pr值的公式如下。
其中bu是所有鏈接到u網頁的網頁集合，網頁v屬于集合bu，l(v)是網頁v的出度。下面我們就用下圖的網頁鏈接關系舉例。
假定a、b、c、d網頁的初始pr值都為0.25，根據上面的計算公式，我們有如下的計算過程。
經過多次的迭代計算后，pr值逐漸穩(wěn)定，即可認為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的隨機瀏覽模型
隨機瀏覽模型是符合用戶上網行為的一種模型。用戶隨機打開一個網頁后，要么點擊這個網頁上的鏈接繼續(xù)網頁的瀏覽，要么隨機轉到另外的一個網頁重新開始新一輪的瀏覽。
為此隨機瀏覽模型引入了一個阻尼系數d來表示用戶點擊此網頁上的鏈接繼續(xù)瀏覽的概率，則1-d就是用戶重新進行新一輪的瀏覽的概率。引入阻尼系數d的計算公式如下。
其中n為整個網頁的數目。
引入阻尼系數的效果為：在原有的有向圖中添加了一個全鏈接的瀏覽關系，這樣就完全解決了簡化模型中出現的排名泄漏和排名下沉的問題。如下圖所示。
其中虛線就是隨機瀏覽模型添加的全鏈接關系。