複雜網絡實驗7：pagerank算法（matlab）

一、什麼是pagerank算法？

1.pagerank算法是一種基于随機遊走的評價網站估值的算法

為什麼？

可以證明：從網絡中随機選出一個節點，順着有向邊行走K步之後，位于節點i的機率，

等于運用pagerank算法k步後得到的節點i的PR值。

這個結論很厲害，寫在書上的應該錯不了，書上也沒給出證明，就先把這個結論當個黑箱，當個結論先記下來

2.pagerank算法的基本思想

網際網路上一個頁面的重要性取決于指向它的其他頁面的數量和品質

初始時給一個網絡内所有頁面配置設定相等的重要性，如果有N個頁面，每個每頁的重要性就是1/N

把整個網絡抽象成一個有向圖，一個頁面看成一個頂點，頁面中的超連結看成是有向邊

如果一個頁面中有3個超連結指向其他3個頁面，那麼這個節點就有三條有向邊指向這三個表示相應頁面的節點

整個網絡經過初始配置設定後，進入疊代，疊代收斂=疊代前等于疊代後（可以用保留小數的方法）

現在的問題就是：

• 初始情況應該怎麼确定？
• 疊代怎麼疊代?
• 算法終止條件怎麼确定？（後面讨論）

#1.初始情況的确定（基本的PageRank算法）

給定所有節點的初始PageRank值（簡稱PR值，下方都使用PR值），滿足

其中下圖部分意思是第0次疊代（初始情況）i節點的PR值

一般初始情況給每個節點配置設定相同的PR值，四個節點，每個節點的初始PR值都是1/4

#2.疊代方法

每次疊代，都是把上一版本所有節點的PR值進行一次修改

修改方法如下

記每個節點的出度為：

意思是第i個節點的出度

周遊每個節點，把目前節點的PR值平分給該點有向邊所指向的那些節點

意思是：目前頁面有一個PR值，假如說目前頁面有三個超連結指向3個頁面，每次疊代就把目前頁面的PR值平分給這三個頁面

有下方的疊代公式

意思是i節點第K次疊代的PR值等于

所有其他節點，經過平分後，流入該節點的PR值

其中，

是鄰接矩陣中的值，j節點和i節點之間存在邊就是1，不存在就是0

再細細品味就能了解到pagerank的基本思想

二、pagerank算法的未修正實作

針對如下有向圖進行分析

（圖1，以下實驗針對該圖）

圖中的數字是最後疊代收斂，進入穩态，最終每個節點的PR值。

初始時每個節點的PR值都是1/8

定義基本的Google矩陣

我們可以對有向圖每一行除以該點的出度，得到這個Google矩陣

疊代規則可以寫成下面這樣的形式

其中

是一個n行1列的向量，通過google矩陣的轉置對上一次疊代進行修正，等到本次疊代的結果

谷歌矩陣每一行是對相應點的出度進行平分的結果

轉置之後，就是每個點經過出度平分，流入該點的PR值比例，不知道能不能了解

你們可以拿着第一個點在腦子裡測試一下是不是這個道理

代碼思路如下：

1.c=pagerank(A,n)函數，傳入初始鄰接矩陣和矩陣規模，傳回最終的PR值向量放入c中

#1.計算每個點的出度

#2.得到google矩陣

#3.初始化PR向量

#4.進入疊代

2.疊代算法單獨拿出來做成一個函數 runpagerrank

c=runpagerank(A1,PR)  傳入谷歌矩陣和上個版本的PR值，經過google矩陣修正得到新的PR值

3.c=pagerank(A,n)代碼如下：

function c=pagerank(A,n)   %傳入鄰接圖A和網絡規模n
%1.計算每個點的出度
outDegree=zeros(n,1);
for i=1:n
    current_outDegree=0;
    for j=1:n
        if A(i,j)>0
            current_outDegree=current_outDegree+1;
        end
    end
    outDegree(i,1)=current_outDegree;
end

%2.基本的pagerank算法，得到的google矩陣A1如下
A1=A;
for i=1:n
    for j=1:n
        if outDegree(i,1)==0                 %如果一個點出度為0，為了防止這個點把整個網路的PR值耗散掉，設定這個點沒有連結的情況下，随機跳轉到其他網絡
            A1(i,j)=1/n;
        else
        A1(i,j)=A1(i,j)/outDegree(i,1);
        end
    end
end
A1
%3.初始化PR向量，使得浏覽每個頁面的機率相同
PR=zeros(n,1);
for i=1:n
    PR(i,1)=1/n;
end
PR
%4.把谷歌矩陣A1轉置，右邊乘上PR矩陣，就是一次疊代
%疊代收斂的意思是，這次疊代和下次疊代結果相同，就停止
num=0;
runpagerank(A1,PR)
while 1
    if round(PR,4)==round(runpagerank(A1,PR),4) %這裡如果不用估值（前4），一直沒法終止算法
        c=PR;
        break;
    else
        PR=runpagerank(A1,PR);
        PR
        num=num+1
    end
end
    
           

4.runpagerank(A1,PR)代碼如下

function c=runpagerank(A1,PR)
c=A1'*PR;
           

5.實驗結果

在外面構造一個圖一的鄰接矩陣A

調用pagerank(A,size(A,1))即可

驗證1節點4/13=？

得到的結果是正确的

三、pagerank算法未修正實作有哪些問題？

1.懸挂節點（Dangling node）

導緻pagerank算法若幹次疊代之後整個網絡所有節點PR值為0

如果圖中有一個點的出度為0，也就是該頁面沒有任何超連結指向其他頁面

在使用PR算法進行一次疊代時，這個點的PR值将被耗散掉

就是說，整個網絡每次疊代都會傳遞給這個出度為0的點一些PR值，而這個出度為0的點沒有可以把自身PR值回饋給整個網絡的途徑，每次疊代都耗散一點，最後完全gg思密達。

2.出部導緻算法的PR值最後全部被出部所吸收

像上圖這樣一個小系統（6号節點和7号節點組成的系統）組成的出部，也沒有把PR值回饋給系統的途徑整個出部隻會向系統索取，而不會反哺系統，簡直人渣，最後也會導緻若幹次疊代後出部吸收了系統所有的PR值，系統其它部分PR值都為0。

3.環裝網絡導緻算法不停循環而無法收斂

在上圖基礎上，如果初始PR值為

（為什麼初始PR值不都設成一樣？這裡隻是想說明這個不斷循環的過程

如果全部設成一樣，下一次疊代大家也都是1/5，馬上就誤判成收斂，不就很撈了？）

那麼PR值疊代過程如下表：

（忽略右上角的馬賽克）

最後就不斷循環，無法收斂，我算法裡的收斂條件是RP值前四位 疊代前和疊代後一樣，最後傳回疊代前的PR值向量

四、pagerank算法的修正實作

修正的随機沖浪者模型：

假設有一個網上的随機沖浪者，他從一個随機選擇的頁面開始浏覽。

如果目前頁面的出度大于零，那麼以機率s(0<s<1)在目前頁面上随機點選某個超文本連接配接，進入下一個頁面，

同時會以機率1-s在整個WWW上完全随機選擇一個頁面作為下一步要浏覽的頁面。（看成是重新輸入網址浏覽）

如果目前頁面的出度為零，那麼完全随機地選擇一個頁面作為下一步要浏覽的頁面。（看成是目前頁面沒有超連結指向其他頁面，那麼隻能在位址欄鍵入網址，進行下一步浏覽）

1.經過修正的模型的疊代規則

意思是第K步疊代i節點的PR值，以s的機率按照之前的方式執行，以（1-s）的機率進行随機浏覽

這裡的

表示如下：

意思是出度大于0，不變

出度等于0，那麼随機浏覽

2.s值的大小确定

可以想象，s值的大小是控制模型按照之前模式浏覽還是随機浏覽的一個滑動值

如果s=0，那麼公式前面一半為0，後面就是1/N

意思就是所有頁面都不點自身的超連結，都選擇在網址欄鍵入網址的方式進行浏覽。

如果s=1,公式後面一半為0，就完全按照未修正模型進行PR的計算。

Page和Brin當初提出PageRank算法時，建議取s=0.85。

這個0.85的結果也不知道他們做了多少工作才得出的，也不知道他們最後怎麼就建議成0.85

反正現在就用0.85來玩吧....

3.算法實作

隻要把之前算法的google矩陣邏輯稍微改一下就好了

就是在第二部分稍微改一下

function c=pagerank1(A,n)   %傳入鄰接圖A和網絡規模n
%1.計算每個點的出度
outDegree=zeros(n,1);
for i=1:n
    current_outDegree=0;
    for j=1:n
        if A(i,j)>0
            current_outDegree=current_outDegree+1;
        end
    end
    outDegree(i,1)=current_outDegree;
end

%2.經過修正的pagerank算法，得到的google矩陣A1如下
A1=A;
for i=1:n
    for j=1:n
        if outDegree(i,1)==0                 %如果一個點出度為0，為了防止這個點把整個網路的PR值耗散掉，設定這個點沒有連結的情況下，随機跳轉到其他網絡
            A1(i,j)=1/n;
        else
        A1(i,j)=A1(i,j)/outDegree(i,1);
        end
    end
end
A1=0.85*A1+0.15*1/n*ones(n)  %修正google矩陣
%3.初始化PR向量，使得浏覽每個頁面的機率相同
PR=zeros(n,1);
for i=1:n
    PR(i,1)=1/n;
end
PR
%4.把谷歌矩陣A1轉置，右邊乘上PR矩陣，就是一次疊代
%疊代收斂的意思是，這次疊代和下次疊代結果相同，就停止
num=0;
runpagerank(A1,PR)
while 1
    if round(PR,4)==round(runpagerank(A1,PR),4)
        c=PR;
        break;
    else
        PR=runpagerank(A1,PR);
        PR
        num=num+1
    end
    if num==73
        break;
    end
end
    
           

五.小結

左圖為修正pagerank結果，右圖為未修正的pagerank結果

可以看到結果大差不差，但是疊代速度那就快很多了。