文章目錄

• • 1. PageRank 的定義
  • • 1.1 基本想法
    • 1.2 PageRank 的基本定義
    • 1.3 PageRank 的一般定義
  • 2. PageRank 的計算
  • • 2.1 迭代算法
    • 2.2 冪法
    • 2.3 代數(shù)算法

PageRank算法是圖的鏈接分析（link analysis）的代表性算法，屬于圖數(shù)據(jù)上的無監(jiān)督學(xué)習(xí)方法。

PageRank算法最初作為互聯(lián)網(wǎng)網(wǎng)頁重要度的計算方法，1996年由Page和Brin提出，并用于谷歌搜索引擎的網(wǎng)頁排序。
事實上，PageRank可以定義在任意有向圖上，后來被應(yīng)用到社會影響力分析、文本摘要等多個問題。
PageRank算法基本想法：

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

1. PageRank 的定義

1.1 基本想法

PageRank是定義在網(wǎng)頁集合上的一個函數(shù)，對網(wǎng)頁給出一個正實數(shù)，表示網(wǎng)頁的重要程度，整體構(gòu)成一個向量，PageRank值越高，網(wǎng)頁就越重要，在互聯(lián)網(wǎng)搜索的排序中可能就被排在前面

• 假設(shè)互聯(lián)網(wǎng)是一個有向圖
• 在其基礎(chǔ)上定義隨機游走模型，即一階馬爾可夫鏈，表示網(wǎng)頁瀏覽者在互聯(lián)網(wǎng)上隨機瀏覽網(wǎng)頁的過程
• 假設(shè)瀏覽者在每個網(wǎng)頁依照連接出去的超鏈接以等概率跳轉(zhuǎn)到下一個網(wǎng)頁，并在網(wǎng)上持續(xù)不斷進行這樣的隨機跳轉(zhuǎn)，這個過程形成一階馬爾可夫鏈
• PageRank表示這個馬爾可夫鏈的平穩(wěn)分布。每個網(wǎng)頁的PageRank 值就是平穩(wěn)概率

1.2 PageRank 的基本定義

給定一個包含 $n$ 個結(jié)點 $v_1，v_2\dots ，v_n$ 的強連通且非周期性的有向圖，在有向圖上定義隨機游走模型，即一階馬爾可夫鏈。
隨機游走的特點是從一個結(jié)點 到有 有向邊連出的所有結(jié)點的轉(zhuǎn)移概率相等，轉(zhuǎn)移矩陣為M。這個馬爾可夫鏈具有平穩(wěn)分布 R, $MR=R$

平穩(wěn)分布 R 稱為這個有向圖的 PageRank。R的各個分量稱為各個結(jié)點的PageRank值

其中$PR\left(v_i\right),i=1,2,?,n,$ 表示結(jié)點 $v_i$ 的 PageRank 值
$$\begin{array}{c}R=?\begin{array}{c}PR\left(v_1\right)\\ PR\left(v_2\right)\\ ?\\ PR\left(v_n\right)\end{array}?\\ \begin{array}{c}\\ PR\left(v_i\right)?0,i=1,2,?,n\\ \\ \sum _{i=1}^{n}PR\left(v_i\right)=1\end{array}\\ \begin{array}{l}\\ PR\left(v_i\right)=\sum _{v_j\in M\left(v_i\right)}\frac{PR\left(v_j\right)}{L\left(v_j\right)},i=1,2,?,n\end{array}\end{array}$$
$M(v_i)$ 表示指向節(jié)點 $v_i$ 的節(jié)點集合，$L(v_j)$ 表示節(jié)點 $v_j$ 連出的有向邊個數(shù)

定理 ：不可約且非周期的有限狀態(tài)馬爾可夫鏈，有唯一平穩(wěn)分布存在，并且當(dāng)時間趨于無窮時狀態(tài)分布收斂于唯一的平穩(wěn)分布。

• 一般的有向圖未必滿足強連通且非周期性的條件
• 比如，在互聯(lián)網(wǎng)，大部分網(wǎng)頁沒有連接出去的超鏈接，也就是說從這些網(wǎng)頁無法跳轉(zhuǎn)到其他網(wǎng)頁。所以PageRank的基本定義不適用

1.3 PageRank 的一般定義

有 n 個結(jié)點的任意有向圖，定義一個一般的隨機游走模型，即一階馬爾可夫鏈。
一般的隨機游走模型的轉(zhuǎn)移矩陣由兩部分的線性組合組成：

• 一部分是有向圖的基本轉(zhuǎn)移矩陣M，表示從一個結(jié)點到其連出的所有結(jié)點的轉(zhuǎn)移概率相等
• 另一部分是完全隨機的轉(zhuǎn)移矩陣，表示從任意一個結(jié)點到任意一個結(jié)點的轉(zhuǎn)移概率都是1/n，線性組合系數(shù)為阻尼因子 $d（0\le d\le 1）$

這個一般隨機游走的馬爾可夫鏈存在平穩(wěn)分布，記作 R。
定義平穩(wěn)分布向量R為這個有向圖的一般PageRank。R由公式 $R=dMR+\frac{1?d}{n}1$ 決定，$1$ 是所有分量為 1 的 n 維向量

$$PR\left(v_i\right)=d?\sum _{v_j\in M\left(v_i\right)}\frac{PR\left(v_j\right)}{L\left(v_j\right)}?+\frac{1?d}{n},i=1,2,?,n$$

一般PageRank的定義意味著互聯(lián)網(wǎng)瀏覽者：

• 在任意一個網(wǎng)頁上，瀏覽者或者以概率 d 決定按照超鏈接隨機跳轉(zhuǎn)，這時以等概率從連接出去的超鏈接跳轉(zhuǎn)到下一個網(wǎng)頁
• 或者以概率（1-d）決定完全隨機跳轉(zhuǎn)，這時以等概率1/n跳轉(zhuǎn)到任意一個網(wǎng)頁
• 第二個機制保證從沒有連接出去的超鏈接的網(wǎng)頁也可以跳轉(zhuǎn)出。這樣可以保證平穩(wěn)分布，即一般PageRank的存在

2. PageRank 的計算

包括迭代算法、冪法、代數(shù)算法。常用的方法是 冪法

2.1 迭代算法

輸入：含有 n 個結(jié)點的有向圖，轉(zhuǎn)移矩陣 M，阻尼因子 d，初始向量 R₀
輸出：有向圖的 PageRank 向量 R

令 $t=0$

計算 $R_{t+1}=dM{R}_t+\frac{1?d}{n}1$

如果 $R_{t+1}$ 與 $R_t$ 充分接近，令 $R=R_{t+1}$，停止迭代

否則，令 $t=t+1$，執(zhí)行步 2

2.2 冪法

輸入：含有 n 個結(jié)點的有向圖，轉(zhuǎn)移矩陣 M，系數(shù) d，初始向量 x₀，計算精度 $\epsilon$
輸出：有向圖的 PageRankR

令 $t=0$，選擇初始向量 $x_0$

計算有向圖的一般轉(zhuǎn)移矩陣 A ，$A=dM+\frac{1?d}{n}\mathbf{E}$，$\mathbf{E}$ 是所有元素為1的n階方陣

迭代并規(guī)范化結(jié)果向量
$$y_{t+1}=A{x}_t$$
$$x_{t+1}=\frac{y_{t+1}}{||y_{t+1}||}$$

當(dāng) $||x_{t+1}?x_t||<\epsilon$ 時，令 $R=x_t$，停止迭代

否則，令 $t=t+1$，執(zhí)行步 3

對 R 進行規(guī)范化處理，使其表示概率分布

2.3 代數(shù)算法

代數(shù)算法 通過一般轉(zhuǎn)移矩陣的逆矩陣計算求有向圖的一般 PageRank
按照PR的一般定義：$$R=dMR+\frac{1?d}{n}1$$
于是有：
$$(I?dM)R=\frac{1?d}{n}1$$
$$R=(I?dM{)}^{?1}\frac{1?d}{n}1$$
這里 $\mathbf{I}$ 是單位矩陣。
當(dāng) $0<d<1$ 時，上面方程的解存在且唯一
可以通過求逆矩陣 $(I?dM{)}^{?1}$ 得到有向圖的一般 PageRank

總結(jié)

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

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