12、网页排名向量更新：迭代聚合算法的应用与优势

网页排名向量更新：迭代聚合算法的应用与优势

1. 近似聚合矩阵与扰动分析

在构建聚合矩阵时，我们不使用精确的删失分布 $s^T$ 来构建精确的聚合矩阵 $C$，而是使用向量 $\tilde{s}^T = \omega^T / \omega^T e$ 来近似 $s^T$，从而构建近似聚合矩阵 $\tilde{C}$。这里，$\delta^T = s^T - \tilde{s}^T$ 和 $E = C - \tilde{C}$ 的量级显然是相同的。

这表明，如果能恰当地对状态进行划分 $S = L \cup \overline{L}$，使得 $\delta^T$ 的量级较小，那么 $\tilde{C}$ 就会接近 $C$，它们各自的平稳分布 $\tilde{\xi}^T$ 和 $\xi^T$ 也会相近，进而保证对于 $i \leq l$，$\tilde{\pi}_i$ 和 $\pi_i$ 相近。然而，马尔可夫链有时对小扰动很敏感，所以在得出这个结论之前需要谨慎。

衡量平稳概率对转移概率变化敏感度的方法有很多，比如转移矩阵次主导特征值的大小接近 1 的程度、各种“条件数”的大小以及平均首达时间的大小等。即使 $\delta^T$（进而 $E$）的分量很小，对于 $i \leq l$，$\tilde{\xi}i$ 和 $\xi_i$（以及 $\tilde{\pi}_i$ 和 $\pi_i$）也可能相差较大。例如，当 $G{12}$ 的量级较小时，$C$ 的次主导特征值接近 1，这会使平稳概率对扰动敏感。当然，如果 $C$ 定义的链条件良好，那么 $\xi^T$ 对小扰动相对不敏感，$\omega^T$ 近似 $\pi^T_2$ 的程度将更直接地反映 $\tild