PageRank算法（二）
原文地址：https://blog.csdn.net/monkey_d_meng/article/details/6556295
說明：這是我學習過程中看到對PageRank來龍去脈解釋非常清晰的博客，博主很厲害，大家可以關注一下原創(chuàng)作者！
一、PageRank算法的簡單舉例
Google PageRank算法的思想精華在于：將一個網(wǎng)頁級別/重要性的排序問題轉化成了一個公共參與、以群體民主投票的方式求解的問題，網(wǎng)頁之間的鏈接即被認為是投票行為。同時，各個站點投票的權重不同，重要的網(wǎng)站投票具有較大的分量，而該網(wǎng)站是否重要的標準還需要依照其PageRank值。這看似是一個矛盾的過程：即我們需要用PageRank值來計算PageRank值~
聽起來有點不可思議，既像是遞歸，又像是迭代，似乎陷入了一個漩渦，Google的創(chuàng)始人佩奇和布林證明了這個過程最終收斂值與初始值無關。遺憾的是我一直都沒有找到這個證明，甚至我把佩奇他們當年那篇論文找出來看也沒有發(fā)現(xiàn)~
對于PageRank的收斂性，我們是可以找到反例的，這說明PageRank至少在某些情況下是不可能收斂的，或者說是收斂不完備的。在本文的第三部分，我們將PageRank的問題轉化為了馬爾可夫鏈的概率轉移問題，其收斂性的證明也即轉化為了馬氏鏈的平穩(wěn)分布是否存在的證明。我們先來看一個簡單的例子：
Google PageRank取值范圍是0~10，為了敘述方便，我們使用0~1的區(qū)間作為度量，這并不會影響我們對PageRank原理的剖析，并且在初始化的時候，我們假設所有網(wǎng)站的PageRank的值是均勻分布的。這意味著，如果有N個網(wǎng)站，那么每個網(wǎng)站的PageRank初始值都是1/N?，F(xiàn)在假設有4個網(wǎng)站A、B、C、D，則它們的初始PageRank都是0.25，它們的鏈接關系如下：
?
?
則初始值PR(A) = PR(B) = PR(C) = PR(D) = 0.25，又因為B、C、D都有指向A的鏈接，因此，它們每人都為A貢獻了0.25的PageRank值，重新計算A的PageRank值為：PR(A) = PR(B) + PR(C) + PR(D) = 0.75，由于B、C和D并沒有外部鏈接指向它們，因此PR(B)、PR(C)、PR(D)在這次計算中將被賦值為0。反復套用PageRank的計算公式，來看一下，這種情況下PageRank的收斂性，在第二次迭代之后，所有的PageRank值就都是0了：
| PageRank | PR(A) | PR(B) | PR(C) | PR(D) |
| 初始值 | 0.25 | 0.25 | 0.25 | 0.25 |
| 第一次迭代后 | 0.75 | 0 | 0 | 0 |
| 第二次迭代后 | 0 | 0 | 0 | 0 |
我們來分析一下這個例子PageRank收斂的情況，由于沒有網(wǎng)站鏈接到D，那么第一次迭代之后PR(D)=0，這將導致PR(B)=0，繼而導致PR(C)=0和PR(A)=0。
?
?
現(xiàn)在來看第個例子，假設網(wǎng)站B還有C鏈接，網(wǎng)站D上有其他三個網(wǎng)站的鏈接。對于B而言的話，它把自己的總價值分散投給了A和C，各占一半的PageRank，即0.125，C和D的情況同理。即一個網(wǎng)站投票給其它網(wǎng)站PageRank的值，需要除以它所鏈接到的網(wǎng)站總數(shù)。此時PageRank的計算公式為：
| PR(A) = PR(B) / 2 + PR(C) / 1 + PR(D) / 3 PR(B) = PR(D) / 3 PR(C) = PR(B) / 2 + PR(D) / 3 PR(D) = 0 |
?
| PageRank | PR(A) | PR(B) | PR(C) | PR(D) |
| 初始值 | 0.25 | 0.25 | 0.25 | 0.25 |
| 第一次迭代后 | 0.4583 | 0.0833 | 0.2083 | 0 |
| 第二次迭代后 | 0.25 | 0 | 0.0417 | 0 |
| 第三次迭代后 | .0.417 | 0 | 0 | 0 |
| 第四次迭代后 | 0 | 0 | 0 | 0 |
PageRank值計算過程的一般步驟可以概括如下：
（1）為每個網(wǎng)站設置一個初始的PageRank值。
（2）第一次迭代：每個網(wǎng)站得到一個新的PageRank。
（3）第二次迭代：用這組新的PageRank再按上述公式形成另一組新的PageRank。
……
當然，我們最關心的問題是，如此迭代下去，這些PageRank的值最終會收斂嗎？我們上述的兩個例子都是收斂的，但是不是所有情況都是如此呢？而且，上述例子中，我們發(fā)現(xiàn)，一旦某個頁面的外部鏈接數(shù)目為0的話，那必然將導致全部網(wǎng)頁最終收斂值為0。
?
二、PageRank算法的“黑洞效應”
為了討論收斂性的問題，我們暫時拋開具體的網(wǎng)站，把問題做一個抽象化的描述，我們可以把網(wǎng)頁之間的關聯(lián)關系理解為是若干張有向圖，圖與圖之間是互不連通的，那我們只考慮每一部分的收斂性，并不會影響其他部分的收斂性。我們考慮把邊權值當作網(wǎng)站所傳遞的PageRank值，則對于任意一個頂點而言，其出邊的權值之和必為1。
一個很顯然的結論是，如果連通圖中有一個頂點的入度為0，則經(jīng)過有限次迭代之后，該連通圖內(nèi)的所有頂點的PageRank均為0，形象的說，這個頂點就像一個黑洞一樣，把整體的PageRank值慢慢地“吸收”了。由于它不對外貢獻任何PR值，所以整體的PR總和是在不斷地減少，直到最終收斂到0。我把它稱之為：PageRank的“黑洞效應”。至于說Google是如何防止這種情況的發(fā)生，畢竟一個網(wǎng)站沒有外鏈是完全有可能的，我也尚未找到確切的答案。不過網(wǎng)上道是有人給出了一種解決辦法：即如果一個網(wǎng)站沒有外鏈，那么就假定該連通圖內(nèi)其余所有的網(wǎng)點都是它的外鏈，這樣我們就避免了整體PageRank值被吸收的現(xiàn)象。
當一個連通圖內(nèi)部每一個頂點入度均大于0時，不難看出，PR值在內(nèi)部流通過程中，整體的PR值是守恒的。如果是存在一個頂點的入度為0呢？通過一次迭代，它的PR值就會變成0，而把它的那部分PR值貢獻給了圖中剩余的部分。所以，最終入度為0的頂點的PR值都將是0，而整體的PR仍然守恒。那么整體的PR值守恒就一定能夠保證每個頂點的PR值最終會收斂嗎？下面看一個簡單的例子：
按照之前的迭代步驟，會得到一個迭代的結果表。這將是一個無限循環(huán)，且不會收斂的過程。
| PageRank | PR(A) | PR(B) | PR(C) | PR(D) |
| 初始值 | 0.25 | 0.25 | 0.25 | 0.25 |
| 第一次迭代后 | 0 | 0.375 | 0.25 | 0.375 |
| 第二次迭代后 | 0 | 0.375 | 0.375 | 0.25 |
| 第三次迭代后 | 0 | 0.25 | 0.375 | 0.375 |
| 第四次迭代后 | 0 | 0.375 | 0.25 | 0.375 |
| 第五次迭代后 | 0 | … | … | … |
其實，同樣的問題我們還可以換一個角度來考慮，因為本質(zhì)上有向圖和矩陣是可以相互轉化的，令A[i][j]表示從頂點i到達頂點j的概率，那么目力的矩陣表示就是：
| 0?????0.5??0?????0.5 0?????0?????1?????0 0?????0?????0?????1 0?????1?????0?????0 |
而我們所給定的初始向量是：(0.25???0.25???????0.25???????0.25)，做第一次迭代，就相當于用初始向量乘以上面的矩陣。第二次迭代就相當于第一次迭代的結果再乘以上面的矩陣……實際上，在隨機過程理論中，上述矩陣被稱為“轉移概率矩陣”。這種離散狀態(tài)按照離散時間的隨機轉移過程稱為馬氏鏈（馬爾可夫鏈，Markov Chain）。設轉移概率矩陣為P，若存在正整數(shù)N，使得P^N>0（每個元素大于0），這種鏈被稱作正則鏈，它存在唯一的極限狀態(tài)概率，并且與初始狀態(tài)無關。
在這里，我們僅僅是非常簡單地討論了一下PageRank的原理，這與Google PageRank的實際算法實現(xiàn)相當甚遠。域名數(shù)據(jù)、內(nèi)容質(zhì)量、用戶數(shù)據(jù)、建站時間等都有可能被考慮進去，從而形成一個完善的算法。
當然，最讓人驚嘆的是，Google的PageRank能夠應對互聯(lián)網(wǎng)所產(chǎn)生的如此海量的網(wǎng)頁信息和實時的變化，并能夠在有限的時間內(nèi)計算出所有網(wǎng)站的PageRank！這里面到底蘊涵著什么樣的奧秘，我也會繼續(xù)地追尋下去！
?
三、PageRank算法的馬爾科夫過程分析
從第二節(jié)的陳述中我們知道，事實上，PageRank值在轉移過程中變化規(guī)律是完全可以用馬爾科夫的狀態(tài)轉移來進行表征的，兩者本質(zhì)屬于同一個問題。則當PageRank值收斂時，即為馬爾可科夫鏈達到平衡分布。推薦大家去讀《隨機過程》的教材，這里不在詳細地討論馬氏鏈的內(nèi)容，只給出相應的結論。
為了形象說明馬氏鏈，這里舉一個例子。假設一{A, B, C}為馬氏鏈，其轉移概率矩陣如下所示：
| 0.7?????????0.1?????????0.2 0.1?????????0.8?????????0.1 0.05???????0.05???????0.9 |
因為該馬氏鏈是不可約的非周期的有限狀態(tài)，平穩(wěn)分布存在，則我們要求其平衡分布為：
| X = 0.7X + 0.1Y + 0.05Z Y = 0.1X + 0.8Y + 0.05Z Z = 0.2X + 0.1Y + 0.9Z X + Y + Z = 1 |
解得上述方程組的平穩(wěn)分布為：X = 0.1765，Y = 0.2353，Z = 0.5882。
既然，說我們把PageRank收斂性問題轉化為了求馬爾可夫鏈的平穩(wěn)分布的問題，那么我們就可以從馬氏鏈的角度來分析問題。因此，對于PageRank的收斂性問題的證明也就迎刃而解了，只需要證明馬氏鏈在什么情況下才會出現(xiàn)平穩(wěn)分布即可。我們可以知道馬氏鏈有三個推論：
推論1.?有限狀態(tài)的不可約非周期馬爾可夫鏈必存在平穩(wěn)分布。
推論2.?若不可約馬爾可夫鏈的所有狀態(tài)是非常返或零常返的，則不存在平穩(wěn)分布。
推論3.?若{Xi}是不可約的非周期馬氏鏈的平穩(wěn)分布，則lim(n→∞)Pj(n) = Xi。
上面的三個推論看不懂不要緊，找本《隨機過程》的書就明白了，這里不再詳細討論了。既然問題得以轉化，那么我們還計算一個實例，看看PageRank是如何工作的。假設這里有相互鏈接關系的7個HTML網(wǎng)頁，并且HTML網(wǎng)頁之間的鏈接關系閉合于這1~7個網(wǎng)頁中，也即是說，除了這些網(wǎng)頁之外，沒有任何鏈接的出入。
那么我們可以很容易地將這個鏈接關系使用數(shù)學的方式表示出來。首先，分析鏈接的關系，列舉出各個鏈接源的ID及其所鏈接的目標ID。
| 鏈接源I D?鏈接目標?ID 1???????????????????2,3 ,4,5, 7 2???????????????????1 3???????????????????1,2 4???????????????????2,3,5 5??????????????????1,3,4,6 6???????????????????1,5 7???????????????????5 |
使用鄰接矩陣的形式表述網(wǎng)頁之間的鏈接關系，A[i][j]=1表示從i到j有鏈接，否則表示無鏈接，A為7*7的矩陣。
| A = [ ????????0, 1, 1, 1, 1, 0, 1; ????????1, 0, 0, 0, 0, 0, 0; ????????1, 1, 0, 0, 0, 0, 0; ????????0, 1, 1, 0, 1, 0, 0; ????????1, 0, 1, 1, 0, 1, 0; ????????1, 0, 0, 0, 1, 0, 0; ????????0, 0, 0, 0, 1, 0, 0; ?] |
我們現(xiàn)假設，每個網(wǎng)頁初始的PageRank均為1，則會形成一個初始的PageRank轉移矩陣。
| A = [ 0,????1/5,????????1/5,????????1/5,????????1/5,????????0,????1/5; 1,????0,???????????0,???????????0,???????????0,???????????0,????0; 1/2,?1/2,????????0,???????????0,???????????0,???????????0,????0; 0,????1/3,????????1/3,????????0,???????????1/3,????????0,????0; 1/4,?0,???????????1/4,????????1/4,????????0,???????????1/4,?0; 1/2,?0,???????????0,???????????0,???????????1/2,????????0,????0; 0,????0,???????????0,???????????0,???????????1,???????????0,????0; ] |
這樣的話，我們就可以按照求馬氏鏈平穩(wěn)分布的方式，求得PageRank收斂結果，方程組為：
| X1 = X2 + X3 / 2 + X5 / 4 + X6 / 2 X2 = X1 / 5 + X3 / 2 + X4 / 3 X3 = X1 / 5 + X4 / 3 + X5 / 4 X4 = X1 / 5 + X5 / 4 X5 = X1 / 5 + X4 / 3 + X6 / 2 + X7 X6 = X5 / 4 X7 = X1 / 5 X1 + X2 + X3 + X4 + X5 + X6 + x7 = 1 |
解這個方程，最終我們得到每個網(wǎng)頁的PageRank收斂值分別為：
X1 = 0.303514，X2 = 0.38286，X3 = 0.32396，X4 = 0.24297，X5 = 0.41231，X6 = 0.10308，X7 = 0.13989。
將PageRank的評價按順序排列，小數(shù)點3位四舍五入，可以得到下表：
| 名次?PageRank???文件ID???發(fā)出鏈接ID??被鏈接ID ??1?????0.304?????1???????2,3,4,5,7???2,3,5,6 ??2?????0.179?????5???????1,3,4,6?????1,4,6,7 ??3?????0.166?????2???????1???????????1,3,4 ??4?????0.141?????3???????1,2?????????1,4,5 ??5?????0.105?????4???????2,3,5???????1,5 ??6?????0.061?????7???????5???????????1 ??7?????0.045?????6???????1,5??????????5 |
讓我們詳細地看一下。ID=1?的文件的?PageRank?是0.304，占據(jù)全體的三分之一，成為了第1位。特別需要說明的是，起到相當大效果的是從排在第3位的?ID=2?頁面中得到了所有的?PageRank（0.166）數(shù)。ID=2頁面有從3個地方過來的反向鏈接，而只有面向?ID=1頁面的一個鏈接，因此（面向ID=1頁面的）鏈接就得到了所有的?PageRank?數(shù)。不過，就因為?ID=1頁面是正向鏈接和反向鏈接最多的頁面，也可以理解它是最受歡迎的頁面吧。
?
?
依據(jù)上圖的PageRank值，我們實際地試著計算一下PageRank的收支，只要將自各頁的流入量單純相加即可。譬如?ID=1?的流入量為：
| ID=1的流入量＝(ID=2發(fā)出的Rank)+(ID=3發(fā)出的Rank) + (ID=5發(fā)出的Rank) + (ID=6發(fā)出的Rank) = 0.166 + 0.141 / 2 + 0.179 / 4 + 0.045 / 2 = 0.30375 |
在誤差范圍內(nèi)PageRank的收支相符合。其他頁面ID的情況也一樣。以上的?PageRank?推移圖正表示了這個收支。沿著各自的鏈接發(fā)出的PageRank等于此頁面原有的PageRank除以發(fā)出鏈接數(shù)的值，而且和各自的頁面的PageRank收支相平衡。
不過，這樣絕妙均衡的本身，對理解線形代數(shù)的人來說當然不會是讓人驚訝的事情。因為這正是“特性值和固有矢量的性質(zhì)”，總之這樣被選的數(shù)值的組就是固有矢量。以上就是?PageRank?的基本原理。?Google?做的就是大規(guī)模地處理這樣的非常特性值問題。
PS：LZ系保研，由于沒有參加考研，像《線性代數(shù)》、《隨機過程》好多年沒摸過了，很多知識都有所遺忘，所以寫的不深入。本文的一些內(nèi)容是參考了別人的博客，自己又加入了些新元素，算是做一次探討。當然，接下來LZ會開始復習一下相關的數(shù)學知識，后續(xù)會重寫本文，以便于讓本文顯得更為Strong~
?
參考的相關博客地址：
http://www.charlesgao.com/?p=157
http://www.kreny.com/pagerank_cn.htm
總結
以上是生活随笔為你收集整理的PageRank算法（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： web项目web接入微信登录
- 下一篇： 屏幕分辨率 VGA、HVGA、QVGA、