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