PageRank计算过程与直觉：从简单例子切入

0 前言

今天我们来介绍图论中，我觉得非常简单优雅的算法 PageRank，老样子，我还是会着重使用例子的方式进行介绍，以便大家能够快速清晰地了解这个算法。在这篇文章中，我们用页面来表示点，链接来表示边。

1 简介

PageRank 是由 Google 的创始人拉里·佩奇和谢尔盖·布林在斯坦福大学开发的一种网页排名算法。它的基本思想是通过分析网页之间的链接关系来评估一个页面的重要性。这个算法有两个非常重要的特性：

• 如果一个页面被很多其他页面链接，则该页面会被认为更重要。
• 如果一个页面链接到其他页面，则它会将自己的重要性“传递”给那些页面。

2 公式

PageRank算法可以用下面的公式来表示：

其中：

• \(PR(p_i)\) 表示页面 \(p_i\) 的 PageRank 值。
• \(d\) 是阻尼因子，代表了用户在浏览网页时遵从跳转链接的概率，通常设置为 0.85。
• \(N\) 是网络中所有页面的数量。
• \(B(p_i)\) 是指向页面 \(p_i\) 的所有页面集合。
• \(L(p_j)\) 表示页面 \(p_j\) 对外发出的链接数量。

在 PageRank 算法中，一开始会为所有页面初始化一个 PageRank 值，一般为 \(\frac{1}{N}\)。然后，使用上述公式，对所有页面的 PageRank 进行更新。更新完后继续更新，直到所有页面的 PageRank 数值收敛。

3 例子

好了又来到重要的例子环节。

假设我们现在有一个页面网络如下：

可以看到，在上面这个例子中，

• 总页面数 \(N = 4\)
• 指向 A 的页面集合 \(B(A) = \left \{ C, \ D \right \}\)
• 指向 B 的页面集合 \(B(B) = \left \{ A, \ D \right \}\)
• 指向 C 的页面集合 \(B(C) = \left \{ B, \ C \right \}\)
• 指向 D 的页面集合 \(B(D) = \left \{ \right \}\)
• 页面 \(A\) 对外发出的链接数量为 \(L(A) = 2\)
• 页面 \(B\) 对外发出的链接数量为 \(L(B) = 1\)
• 页面 \(C\) 对外发出的链接数量为 \(L(C) = 1\)
• 页面 \(D\) 对外发出的链接数量为 \(L(D) = 2\)
• 我们假设 \(d = 0.85\)

首先我们对所有页面的 PageRank 值进行初始化：

• \(PR(A) = 0.25\)
• \(PR(B) = 0.25\)
• \(PR(C) = 0.25\)
• \(PR(D) = 0.25\)

进行第一轮迭代，由公式 \(PR(p_i) = \frac{1-d}{N} + d\sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}\) 有：

• \(PR(A) = \frac{1-0.85}{4} + 0.85 * (\frac{PR(C)}{L(C)} + \frac{PR(D)}{L(D)}) \\ = \frac{1-0.85}{4} + 0.85 * (\frac{0.25}{1} + \frac{0.25}{2}) \\ = 0.0375 + 0.85 * (0.25 + 0.125) = 0.35625\)
• \(PR(B) = \frac{1-0.85}{4} + 0.85 * (\frac{PR(A)}{L(A)} + \frac{PR(D)}{L(D)}) \\ = \frac{1-0.85}{4} + 0.85 * (\frac{0.25}{2} + \frac{0.25}{2}) \\ = 0.0375 + 0.85 * (0.125 + 0.125) = 0.25\)
• \(PR(C) = \frac{1-0.85}{4} + 0.85 * (\frac{PR(A)}{L(A)} + \frac{PR(B)}{L(B)}) \\ = \frac{1-0.85}{4} + 0.85 * (\frac{0.25}{2} + \frac{0.25}{1}) \\ = 0.0375 + 0.85 * (0.125 + 0.25) = 0.35625\)
• \(PR(D) = \frac{1-0.85}{4} = 0.0375\)

类似地，一次一次进行迭代，直到所有页面的 PageRank 值收敛。（比如说设置一个阈值，所有页面的 PageRank 值更新后，与原来的 PageRank 值的变化都小于阈值，我们认为算法收敛结束）

4 迭代公式的直觉理解

• \(\sum_{p_j \in B(p_i)}\)：页面的重要性可以被传递，某页面的重要性接受其他所有链接过来的页面的重要性
• \(\frac{PR(p_j)}{L(p_j)}\)：页面A如果链接了很多页面，那么它传递给每个页面的“重要性”就会相应减少。这是因为它的注意力被分散到了多个页面上。
• \(d\)：阻尼因子 \(d\) 表示用户在浏览网页时继续跟随链接的概率(遵从跳转链接)，而 \(1-d\) 则表示用户随机跳转到任意页面的概率，进而 \(\frac{1-d}{N}\) 则表示用户随机跳转到当前页面的概率

希望上述直觉对大家理解这个公式有帮助。

5 结束

PageRank 的介绍就到这里，希望对大家有帮助，谢谢大家的观看。