PageRank

PageRank Thinking

PageRank 的核心思想是，一个网页的重要性可以通过其他网页对它的引用来衡量。

• 具体来说，如果一个网页被许多其他重要的网页引用（即链接到它），那么这个网页就被认为是更重要的。
• PageRank算法通过分析网页之间的链接关系来为每个网页分配一个权重，称为其“PageRank值”。

PageRank算法的工作原理如下：

1. 首先，将互联网看作一个有向图，其中每个网页是一个节点，链接则是有向边。当网页A链接到网页B时，就在A和B之间建立一条有向边。
2. PageRank算法会为每个网页分配一个初始值，通常是相等的。然后，通过多次迭代来重新分配这些值，直到达到一个稳定状态。
3. 在每次迭代中，每个网页的 PageRank 值会根据其链接到的其他网页的值进行更新。
   1. 具体来说，网页A的 PageRank 值会被分配给它所链接的所有网页，分配的比例取决于A的出度（即A链接到的网页数量）
   2. 因此，一个网页的新 PageRank 值是由
      1. 所有链接到它的网页的当前PageRank值，和
      2. 出度决定的
4. 为了防止循环引用和陷入死循环，PageRank算法还引入了一个名为“阻尼因子”（damping factor）的参数。
   1. 这个参数通常取值为 0.85，意味着一个网页的PageRank值有 85% 来自链接到它的其他网页
   2. 而剩下的15%来自所有网页的均匀分布。

在进行多次迭代后，PageRank值会收敛到一个稳定的状态。这些最终的PageRank值可以作为网页重要性的度量，用于对搜索结果进行排序。

计算举例

假设我们有4个网页：A、B、C和D。它们之间的链接关系如下：

• 网页A链接到网页B和网页C
• 网页B链接到网页C
• 网页C链接到网页A
• 网页D链接到网页A和网页C

首先，我们为每个网页分配一个初始的PageRank值，假设为1。然后，我们使用 PageRank 算法进行迭代更新。在此过程中，我们采用阻尼因子0.85。现在，我们计算每个网页的新PageRank值：

网页A的新PageRank值的计算公式为：

网页A的新PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度)

0.85 是阻尼因子，0.15 是网站的 pagerank 初始值，通常 pagerank 初始值 = 1 - b （即 1- 阻尼因子）。

第1次迭代：

1. 网页A的新 PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度) = 0.15 + 0.85 * (1 / 1) = 1
2. 网页B的新 PageRank值 = 0.15 + 0.85 * (网页A的当前值 / 网页A的出度) = 0.15 + 0.85 * (1 / 2) = 0.575
3. 网页C的新 PageRank值 = 0.15 + 0.85 * [(网页A的当前值 / 网页A的出度) + (网页B的当前值 / 网页B的出度) + (网页D的当前值 / 网页D的出度)] = 0.15 + 0.85 * [(1 / 2) + (1 / 1) + (1 / 2)] = 1.425
4. 网页D的新 PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度) = 0.15 + 0.85 * (1 / 1) = 1

第2次迭代：

1. 网页A的新PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度) = 0.15 + 0.85 * (1.425 / 1) = 1.31125
2. 网页B的新PageRank值 = 0.15 + 0.85 * (网页A的当前值 / 网页A的出度) = 0.15 + 0.85 * (1 / 2) = 0.575
3. ...

第3次迭代：

1. 网页A的新PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度) = 0.15 + 0.85 * (1.51375 / 1) = 1.4366875
2. 网页B的新PageRank值 = 0.15 + 0.85 * (网页A的当前值 / 网页A的出度) = 0.15 + 0.85 * (1.31125 / 2) = 0.7025625
3. 网页C的新PageRank值 = 0.15 + 0.85 * [(网页A的当前值 / 网页A的出度) + (网页B的当前值 / 网页B的出度) + (网页D的当前值 / 网页D的出度)] = 0.15 + 0.85 * [(1.31125 / 2) + (0.575 / 1) + (1 / 2)] = 1.4759375
4. 网页D的新PageRank值 = 0.15 + 0.85 * (网页C的当前值 / 网页C的出度) = 0.15 + 0.85 * (1.51375 / 1) = 1.4366875

我们可以继续进行更多次迭代，直到PageRank值收敛到一个稳定状态。

The “Flow” Model

• 一个重要页面的 "投票 "价值更高
• 如果一个页面被其他重要页面指向，则该页面很重要
• Define a “rank” r_j for page j

$$r_{j}=\sum_{i \rightarrow j} \frac{r_{i}}{\mathrm{~d}_{\mathrm{i}}}$$

就上述图片示例而言，3 equations, 3 unknowns, no constants

• 没有唯一解
• 所有解都以比例因子为模
• 额外的制约因素迫使唯一性
  • 𝒓𝒚 + 𝒓𝒂 + 𝒓𝒎 = 𝟏
  • **Solution: **𝒓𝒚 =𝟓, 𝒓𝒂 =𝟓, 𝒓𝒎 =𝟓

但是，我们需要一种更好的方法来处理大型网络图

Matrix Formulation

PageRank 的矩阵形式是基于线性代数的一种表示方法，它将 PageRank 算法的计算过程表示为矩阵运算。这种表示方法可以让我们更方便地使用线性代数的知识来理解和分析 PageRank 算法

首先，我们需要构造一个链接矩阵 H，矩阵的大小为 N×N（N 为网页数量）。矩阵元素 H(i, j) 的值为：

• 如果网页 j 链接到网页 i，H(i, j) = 1/ L(p_j)，其中 L(p_j) 为网页 j 的出度（即链接到其他网页的数量）。
  • 这就表示，每一列的加和为1
  • 这就表示，H(i, j) 的值是 列标 指向 行标 的值
• 如果网页 j 不链接到网页 i，H(i, j) = 0

1681885244414.png

Problems

• 有些页面是死胡同「Dead Ends」（没有外链）：死胡同页面（Dead Ends）：这类页面没有任何出链（即没有指向其他页面的链接）。由于这种页面不能将其权重分配给其他页面，它们会导致权重“泄漏”。
• Spider traps: 这是一组页面，其所有的出链都指向该组内的其他页面，不指向组外的任何页面。在这种情况下，权重会在这组页面之间循环流动，最终导致该组页面吸收了所有的权重。
  • 这同样会影响 PageRank 算法的性能和准确性，因为在这个过程中，权重无法正确地分配给其他页面。

为了解决这两种问题，PageRank 算法引入了阻尼因子（Damping Factor）。

Dead Ends

谷歌对蜘蛛陷阱的解决方案：在每个时间步骤，"投票 "有两个选项

• With prob. b, follow a link at random
• With prob. **1-**b, jump to some random page

Common values for b are in the range 0.8 to 0.9

“投票”将在几个时间步内传送出蜘蛛陷阱

Spider Traps

• 瞬移：遵循随机传送链接，概率为1.0，远离死胡同。
• 相应地调整矩阵

1681894733521.png

为什么传送可以解决问题

• 蜘蛛陷阱不是问题，但有了陷阱，PageRank分数就不是我们想要的了
• 死胡同是个问题，矩阵不是列随机的，所以我们的初始假设没有得到满足（SUM = 1)
• 解决方案：当没有地方可去时，总是通过传送来使矩阵列随机化。

1681895764048.png

**What is **b? In practice b =0.8 ~ 0.9 (make 5 steps on avg., jump)

1681895842484.png