信息检索与数据挖掘 | （九）Link Analysis（链接分析）

📚链接分析

• 将链接看做投票，从重要的网站来的链接其权重更高，所以是递归定义的。

• 如果网页j权重为rj，有n个出边，每个出边的权重为rj/n，而网页j的自身权重为所有入边的权重之和。定义如下：
  

• 3个未知数3个方程没有唯一解，都是free的，所以可以引入限制sum=1

📚随机矩阵

• 使用矩阵表达，r=Mr:

• 该随机邻近矩阵M每列求和为1，对于向量r来说，列元素求和为1，ri表示i的重要性评分。同时r是M的特征向量，对应的特征值为1，由于1是M的最大特征值，所以可以使用幂迭代法对r进行快速求解：

📚random walk

• t时刻，浏览者在网页i，在t+1时刻，从i的超链接中随机选择一个作为下一个浏览的网页，选择每一个网页的概率是一致的$p(t+1)=M\cdot p(t)$。

• 假设随机游走达到一个状态$p(t+1)=M\cdot p(t)=p(t)$时，称pt为随机游走的稳定分布。

• 我们的原始r向量满足r=Mr，所以r就是随机游走的稳定分布。

• 满足确定条件的图来说其稳定分布是存在且唯一的，且无论初始向量是什么最后一定会到达平稳分布

📚Google formulation

• 原来表达形式的问题：不一定会收敛，或者收敛不到我们想要的结果

• 可能存在的两种特殊情况：

  1. dead end：没有出边，随机行走没有下一个点可以选择，容易造成泄漏

  2. spider traps：环，所有的出边都在环内，将被困在环中，最终，spider trap吸收了所有的importance

• 举例：如果走到m，则不会跳出，将一直访问m，最后r向量收敛为[0,0,1]。
  

  • 解决方法：随机跳转teleports

    • 在每一个时间t中，用户有两种选择，以概率beta随机选择一个连接进行随即游走，或者以概率$1-\beta$进行随机跳转，$\beta$一般在0.8-0.9之间。进而用户可以跳出spider trap。
    • 同时对于dead-ends来说用户直接执行随机跳转，此时访问其他连接的概率为1/N。

  • 理解

    • spider-traps不是问题，但是trap的pagerank 评分不是我们想要的，所以我们使用随机跳转在有限步内跳出trap，不会被困在里面

    • dead-ends是一个问题，因为此时列向量不是随机向量，不满足初始条件，所以我们在之上执行随机游走，将列向量变为随机向量

    • 最后公式变为：

    • 此时矩阵A可以写为：

    • 从而$r=A\cdot r$，依然可以使用幂迭代法，实际中$\beta$=0.8

  

---

• 补充博客：pagerank算法实现
• PageRank算法中Power Iteration的解释。
  • Power Iteration的基本思想是通过不断迭代更新网页的权重值，直到收敛。
  • 以下是Power Iteration算法的基本步骤：
    • 初始化：将所有网页的初始PageRank值设置为相同的数值，通常为1/N，其中N是网页的总数。
    • 迭代计算：重复进行以下步骤，直到收敛为止：
      • 对于每个网页i，根据其当前的PageRank值和其出链的数量来计算对其他网页的贡献值（即将自己的PageRank值平均分配给其出链的网页）。
      • 将网页i的贡献值累加到其每个入链网页j的PageRank值上。
      • 对每个网页j，根据收到的所有入链网页的贡献值来更新其新的PageRank值。
      • 收敛判定：当所有网页的PageRank值变化小于设定的阈值时，算法收敛。
  • Power Iteration的核心思想是通过不断传递和累积网页权重值，直到每个网页的PageRank值稳定下来。