目錄

• • 一、pagerank簡介
  • • 兩個重要假設
  • 二、pagerank算法
  • • 公式定義
    • 計算演示
    • 矩陣化計算
  • 三、存在的兩個問題
  • • 問題1.Dead Ends
    • 問題2.Spider Traps

一、pagerank簡介

PageRank算法的基本想法是在有向圖上定義一個隨機游走模型，即一階馬爾可夫鏈，描述隨機游走者沿著有向圖隨機訪問各個結點的行為。在一定條件下，極限情況訪問每個結點的概率收斂到平穩分布，這時各個結點的平穩概率值就是其PageRank值，表示結點的重要度。PageRank 是遞歸定義的，PageRank 的計算可以通過迭代算法進行。

入鏈數：指向該節點的鏈接數
出鏈數：由該節點指出的鏈接數
以上圖為例：A的入鏈數為1，出鏈數為3，所以將由A指向其他節點的邊權重設置為1/3，表示A訪問B、C、D節點的概率均為1/3

兩個重要假設

• 數量假設:在Web圖模型中，如果一個頁面節點接收到的其他網頁指向的入鏈數量越多，那么這個頁面越重要。
• 質量假設:指向頁面A的入鏈質量不同，質量高的頁面會通過鏈接向其他頁面傳遞更多的權重。所以越是質量高的頁面指向頁面A，則頁面A越重要。

二、pagerank算法

公式定義

• PR（a）表示當前節點a的PR值
• PR（Ti）表示其他各個節點（能夠指向a）的PR值
• L（Ti）表示其他各個節點（能夠指向a）的出鏈數
• i代表當前時刻或迭代次數

計算演示

接下來以下圖為例進行計算演示：

將四個節點的初始PR都設置為1/4

根據每一個節點（a）的入鏈節點(Ti)的PR值及出鏈數和自身(a)的PR值

不斷進行迭代，直到PR值不再發生變化

以A為例：
A有兩個入鏈節點C（出鏈數為1，PR=1/4）和D（出鏈數為2，PR=1/4）由計算公式得到：i=1時刻的PR（A） = (1/4)/1 + (1/4)/2 = 3/8
其余節點計算方法類似，不作贅述。

矩陣化計算

該有向圖的鄰接矩陣如下所示：

借助鄰接矩陣（轉移矩陣）的表示方式，我們可以簡化上述計算，將四個節點的PR值轉化為V向量，并于轉移矩陣相乘，可以得到新一輪的PR值向量

由此可以得到每一步PR值迭代的結果為：MV， MMV， MMM*V 最終會收斂為M‘ * V（詳細數學證明，有興趣可以百度查詢）

三、存在的兩個問題

問題1.Dead Ends

如上圖所示：B沒有任何出鏈，這就是Dead Ends,Dead Ends會導致網站權重變成0.

最樸素的想法是：對全是0的列的每一個元素加上1/n（n為節點個數）
對M進行修正

問題2.Spider Traps

如上圖所示，A節點與其它節點之間沒有出鏈，這就是Spider Traps，這將導致網站權重變為像一個節點偏移（經過多輪迭代后，A的權重越來越大，趨近于1）
需要對M進行修正：

如上圖所示仍有β的概率訪問出鏈頁面，但剩下（1 -β）的概率會隨機跳轉到其他頁面，防止一直從A跳轉到A的情況

總結

以上是生活随笔為你收集整理的pagerank算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。