一、簡(jiǎn)述：

PageRank算法是一個(gè)迭代求解算法，可以處理網(wǎng)頁(yè)排名（根據(jù)網(wǎng)頁(yè)的重要性進(jìn)行排序）、社會(huì)影響力分析、文本摘要 等問(wèn)題。

????????PageRank算法在1996年由Page和Brin提出

????????PageRank適用于解決用有向圖表示的圖數(shù)據(jù)

---

二、各節(jié)點(diǎn)重要性的迭代計(jì)算公式：

PageRank算法是在圖上執(zhí)行一個(gè)隨機(jī)游走模型，根據(jù)隨機(jī)游走者 在有向圖上 通過(guò)對(duì) 節(jié)點(diǎn)訪問(wèn)次數(shù)或訪問(wèn)概率 的高低?來(lái)判斷有向圖上各個(gè)節(jié)點(diǎn)的重要程度

首先給出算法的迭代公式，而后用一個(gè)實(shí)例對(duì)該迭代公式的各個(gè)部分的意義進(jìn)行解釋：

對(duì)于各個(gè)節(jié)點(diǎn)，其重要程度（其被訪問(wèn)概率）可以按以下公式迭代計(jì)算得出：?

（以節(jié)點(diǎn)X為例）

其中：

PR（X）表示節(jié)點(diǎn)的PR值，即節(jié)點(diǎn) X 被訪問(wèn)到的概率，當(dāng)?shù)Y(jié)束后，PR（X）則代表節(jié)點(diǎn)X的重要程度

d?表示?阻尼系數(shù)，指用戶達(dá)到了當(dāng)前節(jié)點(diǎn)后，愿意沿圖上的出邊情況 挑選任一節(jié)點(diǎn) 繼續(xù)向后游走的概率

?表示?在圖上指向節(jié)點(diǎn)X的節(jié)點(diǎn)

?表示?節(jié)點(diǎn)的出度

---

三、用一個(gè)實(shí)例來(lái)解釋公式的各個(gè)部分：? ? ? ??

最初的PageRank算法是用于對(duì)網(wǎng)頁(yè)的重要程度進(jìn)行排名，那么我們就以網(wǎng)頁(yè)排名作為該算法的一個(gè)實(shí)際例子對(duì)迭代公式的各部分進(jìn)行解釋：

????????在我們?cè)L問(wèn)網(wǎng)頁(yè)的時(shí)候，網(wǎng)頁(yè)A可能會(huì)鏈接到其他網(wǎng)頁(yè)上，比如鏈接到網(wǎng)頁(yè)B和網(wǎng)頁(yè)C。如果將這種網(wǎng)頁(yè)間的鏈接關(guān)系體現(xiàn)在圖結(jié)構(gòu)數(shù)據(jù)上的話：那么，在圖數(shù)據(jù)中，網(wǎng)頁(yè)A、B、C均作為節(jié)點(diǎn)出現(xiàn)，且由于網(wǎng)頁(yè)A可以鏈接到網(wǎng)頁(yè)B和網(wǎng)頁(yè)C，那么，在圖上節(jié)點(diǎn)A應(yīng)有兩條出邊，分別指向節(jié)點(diǎn)B和節(jié)點(diǎn)C。

????????現(xiàn)在有如下的網(wǎng)頁(yè)間的鏈接關(guān)系：

????????如圖1示，有ABCD四個(gè)網(wǎng)頁(yè)，網(wǎng)頁(yè)間的鏈接關(guān)系有：A鏈接到BCD；B鏈接到AD；C鏈接到A；D鏈接到C

? ? ? ? PageRank算法的核心思想就是：假設(shè)有一個(gè)隨機(jī)游走者，在圖上進(jìn)行隨機(jī)游走。隨機(jī)游走者經(jīng)過(guò)多次游走后，對(duì)不同的節(jié)點(diǎn)有著不同的訪問(wèn)次數(shù)。顯然，隨機(jī)游走者訪問(wèn)次數(shù)多的節(jié)點(diǎn)有著更高的重要性。算法就是在模擬隨機(jī)游走者在圖上的隨機(jī)游走過(guò)程，所以每次算法對(duì)各個(gè)節(jié)點(diǎn)PR值的迭代更新都對(duì)應(yīng)著隨機(jī)游走者在圖上的一次隨機(jī)游走。

PS：隨機(jī)游走者的"游走"體現(xiàn)為：如圖 1 示若隨機(jī)游走者當(dāng)前所處位置為節(jié)點(diǎn)A，那么，隨機(jī)游走者可以向BCD三個(gè)節(jié)點(diǎn)進(jìn)行下一步的游走；隨機(jī)游走者的"隨機(jī)"體現(xiàn)在：隨機(jī)游走者可以按照概率去隨機(jī)選擇下一個(gè)要游走到的節(jié)點(diǎn)

（一）常規(guī)情況：

????????直觀來(lái)感受，若當(dāng)前隨機(jī)游走者在網(wǎng)頁(yè)B上，由于網(wǎng)頁(yè)B有兩條出邊分別鏈接到網(wǎng)頁(yè)A和D，那么，它有1/2的概率跳轉(zhuǎn)到網(wǎng)頁(yè)A，有1/2的概率跳轉(zhuǎn)到網(wǎng)頁(yè)D。由于網(wǎng)頁(yè)B沒(méi)有對(duì)網(wǎng)頁(yè)C的跳轉(zhuǎn)鏈接，所以圖數(shù)據(jù)上BC兩節(jié)點(diǎn)間沒(méi)有邊，所以由網(wǎng)頁(yè)B跳轉(zhuǎn)到網(wǎng)頁(yè)C的概率為0

? ? ? ? 因此，PageRank算法定義，對(duì)于一個(gè)網(wǎng)頁(yè)，若它可以跳轉(zhuǎn)到k個(gè)其他網(wǎng)頁(yè)上去（即，它在圖上有k條出邊），那么它跳轉(zhuǎn)到這k個(gè)網(wǎng)頁(yè)的概率都是 1/k

????????以圖1為例，先初始化每個(gè)網(wǎng)頁(yè)的被訪問(wèn)概率值PR=1，

????????即：PR（A）=PR（B）=PR（C）=PR（D）=1

然后，對(duì)各個(gè)節(jié)點(diǎn)進(jìn)行隨機(jī)游走分析：

????????如果隨機(jī)游走者想訪問(wèn)到網(wǎng)頁(yè)A，那么要分別從：網(wǎng)頁(yè)B以1/2的概率鏈接到節(jié)點(diǎn)A；從網(wǎng)頁(yè)C以1/1的概率鏈接到節(jié)點(diǎn)A；從網(wǎng)頁(yè)D以0的概率鏈接到節(jié)點(diǎn)A。然后分別代入訪問(wèn)網(wǎng)頁(yè)BCD的訪問(wèn)概率值 與 對(duì)應(yīng)各個(gè)網(wǎng)頁(yè)鏈接到網(wǎng)頁(yè)A的概率相乘，將上述三種情況發(fā)生的概率加和 得到 最終可以訪問(wèn)網(wǎng)頁(yè)A的訪問(wèn)概率。

因此，各個(gè)節(jié)點(diǎn)的PR值迭代公式應(yīng)為?：

其中：

?PR（X）表示?節(jié)點(diǎn)的PR值，即節(jié)點(diǎn)X被訪問(wèn)到的概率，當(dāng)?shù)Y(jié)束后，PR（X）則代表節(jié)點(diǎn)X的重要程度

?表示?在圖上指向節(jié)點(diǎn) X 的節(jié)點(diǎn)

?表示??節(jié)點(diǎn)的出度

????????每次迭代時(shí)，由于圖結(jié)構(gòu)不變，所以計(jì)算各節(jié)點(diǎn)的訪問(wèn)概率時(shí)，只有對(duì)應(yīng)鏈接到該節(jié)點(diǎn)的對(duì)應(yīng)節(jié)點(diǎn)PR值在變動(dòng)，所以，為了加速計(jì)算，很自然的想到用矩陣來(lái)存儲(chǔ)圖的鏈接結(jié)構(gòu)，我們稱該矩陣為轉(zhuǎn)移矩陣M

若拓?fù)鋱D上有n各個(gè)節(jié)點(diǎn)，那么轉(zhuǎn)移矩陣M的大小應(yīng)該為n*n的方陣。

如果網(wǎng)頁(yè) j 有 k 個(gè)出鏈，那么對(duì)于每一個(gè)出鏈所指向的網(wǎng)頁(yè) i ，其 M[i][j] = 1/k

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?對(duì)于沒(méi)有被出鏈指向的網(wǎng)頁(yè) t , 其 M[t][j] = 0

?那么，對(duì)于本圖結(jié)構(gòu)，矩陣M為：

第一次迭代可以計(jì)算為：?

?表示第 i 次迭代后的各個(gè)節(jié)點(diǎn)的訪問(wèn)概率；

“?? ” 表示數(shù)值的點(diǎn)乘；表示矩陣乘法

初始時(shí)，

那么經(jīng)過(guò)一次迭代后，

按這種方式迭代10次，各節(jié)點(diǎn)的PR值變化如下：

迭代1000次，各點(diǎn)的PR值分別為：

PR(A)=1.494391 PR(B)=0.498127 PR(C)=1.245322 PR(D)=0.747192

對(duì)應(yīng)代碼如下：

#include <iostream> using namespace std;int main() {double matrix[4][4]={0,0.5,1,0 , 0.33333,0,0,0 , 0.33333,0,0,1 , 0.33333,0.5,0,0 };double PR[4]={1,1,1,1};double PRtt[4]={0,0,0,0};/*for(int i=0;i<4;i++)for(int j=0;j<4;j++){printf("%f ",matrix[i][j]);}*/for(int num=0;num<1000;num++){for(int i=0;i<4;i++){double tt=0;for(int j=0;j<4;j++){tt += matrix[i][j]*PR[j];}PRtt[i]=tt;}PR[0]=PRtt[0];PR[1]=PRtt[1];PR[2]=PRtt[2];PR[3]=PRtt[3]; //printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);}printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);return 0; }

注意：

“每一輪迭代”的意思是，對(duì)節(jié)點(diǎn)ABCD的PR值都進(jìn)行了一次更新。

????????在上述的這種迭代方式中，對(duì)于第 i 輪的迭代：對(duì)每個(gè)節(jié)點(diǎn)的PR值進(jìn)行更新的時(shí)候，都是用的上一輪（即 i-1 輪次）中各個(gè)節(jié)點(diǎn)的PR值進(jìn)行計(jì)算的。即：在第i輪迭代中，雖然對(duì)于節(jié)點(diǎn)B來(lái)說(shuō)，新的PR值已經(jīng)計(jì)算完了，但是，在計(jì)算CD節(jié)點(diǎn)的PR值時(shí)，仍舊采用的是B節(jié)點(diǎn)在 i-1 輪次的舊PR值。

????????那么，讀者可能會(huì)有疑惑，如果實(shí)時(shí)更新，在同一輪中，用最新的節(jié)點(diǎn)PR值對(duì)接下來(lái)的其他節(jié)點(diǎn)進(jìn)行更新會(huì)產(chǎn)生與上述方法有什么不同么？

我們還是采用圖 1 對(duì)應(yīng)的圖結(jié)構(gòu)進(jìn)行數(shù)值上的對(duì)比。只不過(guò)在這次的更新方式上，即使在同一輪，PR（A）的值計(jì)算結(jié)束，接下來(lái)計(jì)算PR（B）的值時(shí)選擇用剛剛得到的 更新后的 新的 PR（A）的值。對(duì)同一輪的其它節(jié)點(diǎn)的計(jì)算方法同理。

那么，代碼如下：

#include <iostream> using namespace std;int main() {double matrix[4][4]={0,0.5,1,0 , 0.33333,0,0,0 , 0.33333,0,0,1 , 0.33333,0.5,0,0 };double PR[4]={1,1,1,1};/*for(int i=0;i<4;i++)for(int j=0;j<4;j++){printf("%f ",matrix[i][j]);}*/for(int num=0;num<10;num++){for(int i=0;i<4;i++){double tt=0;for(int j=0;j<4;j++){tt += matrix[i][j]*PR[j];}PR[i]=tt;} printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);}//printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);return 0; }

按這種方式迭代10次，各節(jié)點(diǎn)的PR值變化如下：

迭代1000次，各點(diǎn)的PR值分別為：

PR(A)=1.655606 PR(B)=0.551863 PR(C)=1.379663 PR(D)=0.827795

這樣一對(duì)比，雖然最終對(duì)于這四個(gè)節(jié)點(diǎn)計(jì)算得來(lái)的PR值不同，但是迭代后得出的網(wǎng)頁(yè)節(jié)點(diǎn)排名是相同的：A>C>D>B。同時(shí)，對(duì)于收斂速度來(lái)看，僅對(duì)該圖1對(duì)應(yīng)的例子來(lái)說(shuō)，是第一種方法收斂速度更快。

? ? ? ? 但，直覺(jué)上，我還是會(huì)覺(jué)得采用第二種方式來(lái)更新各個(gè)節(jié)點(diǎn)的PR值更好一些，所以接下來(lái)的演示會(huì)采用第二種方式。

（二）非常規(guī)情況：終止點(diǎn)問(wèn)題? ?

上述的PageRank算法可以收斂，需要滿足一個(gè)條件：

? ? ? ? · 處理的圖是強(qiáng)連通圖，即，從任意節(jié)點(diǎn)可以到達(dá)其他的節(jié)點(diǎn)? ? ? ??

但是顯然網(wǎng)頁(yè)節(jié)點(diǎn)間的相互鏈接組成的圖，或者其他現(xiàn)實(shí)生活中產(chǎn)生的拓?fù)鋱D是不一定滿足這種強(qiáng)連接性的?？傆幸恍┚W(wǎng)頁(yè)不指向任何其他的網(wǎng)頁(yè)節(jié)點(diǎn)，即，該網(wǎng)頁(yè)節(jié)點(diǎn)在拓?fù)鋱D上沒(méi)有任何的出邊。

? ? ? ? 此時(shí)，如果仍舊按照上述的PageRank算法，那么，隨機(jī)游走者到達(dá)這樣的網(wǎng)頁(yè)節(jié)點(diǎn)后就會(huì)走投無(wú)路，隨著一次又一次的迭代，隨機(jī)游走者不斷地到達(dá)這個(gè)不指向任何其他網(wǎng)頁(yè)節(jié)點(diǎn)的 “終止點(diǎn)網(wǎng)頁(yè)” ，這就會(huì)導(dǎo)致在迭代過(guò)程中，前面累積的轉(zhuǎn)移概率越變?cè)叫?#xff0c;最終變?yōu)?。
? ? ? ? 我們對(duì)圖 1 進(jìn)行修改，將節(jié)點(diǎn)C →節(jié)點(diǎn)A的邊去掉，得到圖 2 。觀察圖 2 我們會(huì)發(fā)現(xiàn)此時(shí)的節(jié)點(diǎn)C就是一個(gè)“終止點(diǎn)”，在拓?fù)鋱D上，節(jié)點(diǎn)C沒(méi)有任何的出邊。

那么 ，此時(shí)的轉(zhuǎn)移矩陣M為：

按這種方式迭代10次，各節(jié)點(diǎn)的PR值變化如下：

可以很明顯的看出來(lái)，各點(diǎn)的PR值都在逐漸地變?yōu)?

（三）非常規(guī)情況：陷阱問(wèn)題

網(wǎng)頁(yè)間的鏈接情況除了上述的終止點(diǎn)問(wèn)題以外，還有一種情況就是，某個(gè)節(jié)點(diǎn)只存在一條唯一的出邊，并且這條出邊指向自己。如下圖3所示：

????????如圖3所示的這種情況下，隨機(jī)游走者到達(dá)節(jié)點(diǎn) C 后就無(wú)法進(jìn)入其他的網(wǎng)頁(yè)節(jié)點(diǎn)，相當(dāng)于被困在了網(wǎng)頁(yè)節(jié)點(diǎn) C 處。 所以，隨著迭代的進(jìn)行，轉(zhuǎn)移概率會(huì)全部集中到節(jié)點(diǎn) C 對(duì)應(yīng)的網(wǎng)頁(yè)上。這樣會(huì)使得網(wǎng)頁(yè)排名無(wú)效。

按照上述的PageRank算法，圖三所示的轉(zhuǎn)移矩陣M應(yīng)為：

按這種方式迭代10次，各節(jié)點(diǎn)的PR值變化如下：

?可以明顯的看出來(lái)，除了陷阱節(jié)點(diǎn)C以外，其他節(jié)點(diǎn)的PR值都顯著的變?yōu)榱?。

（四）解決終止點(diǎn)和陷阱點(diǎn)問(wèn)題

? ? ? ? 上面過(guò)程中，我們認(rèn)為隨機(jī)游走者是一個(gè)盲目的，只按照節(jié)點(diǎn)的出邊情況進(jìn)行盲目游走的游走者

????????但是，真實(shí)情況下的上網(wǎng)者并不會(huì)如此盲目

????????所以，我們用隨機(jī)游走者模擬上網(wǎng)者時(shí)，當(dāng)它游走到一個(gè)終止點(diǎn)的網(wǎng)頁(yè)時(shí)，它可以選擇重新在瀏覽器搜索欄中輸入一個(gè)新的網(wǎng)址再次進(jìn)行游走；當(dāng)它游走到一個(gè)陷阱節(jié)點(diǎn)時(shí)，它同樣可以采用向?yàn)g覽器中搜索欄中輸入一個(gè)新網(wǎng)址的方式跳出陷阱再次進(jìn)行游走。

????????當(dāng)然，向?yàn)g覽器中輸入的新網(wǎng)址可以是導(dǎo)致當(dāng)前游走終止的終止點(diǎn)網(wǎng)頁(yè)或?qū)е掠巫呦萑胙h(huán)的陷阱點(diǎn)網(wǎng)頁(yè)，但也有可能是 讓游走者進(jìn)入新的網(wǎng)頁(yè)，從而跳出終止或者陷阱情況的新網(wǎng)絡(luò)節(jié)點(diǎn)。

為了達(dá)到這樣的目標(biāo)，對(duì)?“（一）常規(guī)情況 ”中提出的節(jié)點(diǎn)PR值的迭代計(jì)算公式進(jìn)行更新：

? ? ? ? 假設(shè)拓?fù)鋱D上的網(wǎng)頁(yè)節(jié)點(diǎn)有N個(gè)，那么游走者通過(guò)在搜索欄中輸入網(wǎng)址到達(dá)某個(gè)網(wǎng)頁(yè)節(jié)點(diǎn)的概率為 1/N

? ? ? ? 同時(shí)，假設(shè)游走者每一步游走時(shí)查看當(dāng)前網(wǎng)頁(yè)（或者說(shuō)，按照當(dāng)前網(wǎng)頁(yè)給出的鏈接進(jìn)一步訪問(wèn)后面的網(wǎng)頁(yè)）的概率為 d，那么，他拒絕查看當(dāng)前網(wǎng)頁(yè)（或者說(shuō)，拒絕按照當(dāng)前網(wǎng)頁(yè)所給出的鏈接進(jìn)一步訪問(wèn)后面網(wǎng)頁(yè)，而是選擇從瀏覽器搜索欄中隨機(jī)輸入某一網(wǎng)頁(yè)地址進(jìn)行訪問(wèn)）的概率為 (1-d)?

那么，各個(gè)節(jié)點(diǎn)的PR值迭代計(jì)算公式由原來(lái)的：

變?yōu)?#xff1a;

????????所以，很明顯，當(dāng)隨機(jī)游走者拒絕按照當(dāng)前網(wǎng)頁(yè)所給出的鏈接進(jìn)一步訪問(wèn)后面網(wǎng)頁(yè)，而是選擇從瀏覽器搜索欄中隨機(jī)輸入某一網(wǎng)頁(yè)地址進(jìn)行訪問(wèn)，那么拓?fù)鋱D中網(wǎng)頁(yè)節(jié)點(diǎn)的數(shù)目為n，那么，進(jìn)入某任一網(wǎng)頁(yè)節(jié)點(diǎn)的概率自然就是：

????????而由于 按照當(dāng)前網(wǎng)頁(yè)給出的鏈接進(jìn)一步訪問(wèn)后面的網(wǎng)頁(yè) 的概率為 d，所以，原來(lái)的PR值迭代公式前面需要再一同乘上參數(shù)d。

那對(duì)于更新過(guò)的PR值結(jié)算迭代公式，其代碼如下：?

#include <iostream> using namespace std;int main() {double matrix[4][4]={0,0.5,0,0 , 0.33333,0,0,0 , 0.33333,0,1,1 , 0.33333,0.5,0,0 };double PR[4]={1,1,1,1};double d=0.85; //阻尼系數(shù)int N=4; //節(jié)點(diǎn)個(gè)數(shù)/*for(int i=0;i<4;i++)for(int j=0;j<4;j++){printf("%f ",matrix[i][j]);}*/for(int num=0;num<10;num++){for(int i=0;i<4;i++){double tt=0;for(int j=0;j<4;j++){tt += matrix[i][j]*PR[j];}PR[i]=tt*d + (1-d)/ N ;} printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);}//printf("PR(A)=%f PR(B)=%f PR(C)=%f PR(D)=%f\n",PR[0],PR[1],PR[2],PR[3]);return 0; }

按這種方式迭代10次，各節(jié)點(diǎn)的PR值變化如下：

迭代1000次后的結(jié)果如下：?

所以，這四個(gè)網(wǎng)頁(yè)間的重要性排名為：C>D>A>B

?

參考鏈接：https://blog.csdn.net/gamer_gyt/article/details/47443877

總結(jié)

以上是生活随笔為你收集整理的PageRank算法 -- 图算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。