algorithm - quadratic_error 变量在 Google 的 PageRank 算法中的作用是什么？

Question

在 wikipedia 上有 Googles 的 PageRank 的实现。 :

% Parameter M adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j' sum(i, M_i,j) = 1
% Parameter d damping factor
% Parameter v_quadratic_error quadratic error for v
% Return v, a vector of ranks such that v_i is the i-th rank from [0, 1]

function [v] = rank(M, d, v_quadratic_error)

N = size(M, 2); % N is equal to half the size of M
v = rand(N, 1);
v = v ./ norm(v, 2);
last_v = ones(N, 1) * inf;
M_hat = (d .* M) + (((1 - d) / N) .* ones(N, N));

while(norm(v - last_v, 2) > v_quadratic_error)
        last_v = v;
        v = M_hat * v;
        v = v ./ norm(v, 2);
end

endfunction

我无法弄清楚 quadratic_error 的用途。维基百科和文章的算法规范中均未对其进行描述。

Answer 1

看起来是收敛测试。当v和last_v的L₂差不超过的值时，while循环结束v_quadratic_error.

这里有更多的解释。首先，请注意 M_hat 是一个矩阵，v 是一个向量。 while 循环将 v 替换为乘积 M_hat * v(归一化为单位向量)。当一次迭代引起的 v 变化足够小时，循环结束。这就是“融合”在这种情况下的含义。

这似乎是标准 power iteration用于查找与矩阵的主要特征值对应的特征向量的循环(在本例中为 M_hat)。在不了解整体算法(我不打算研究)的情况下，我不能说为什么这个计算有用。