Google的PageRank算法中quadratic_error變量的作用是什麼？

Question

有谷歌的網頁級別上wikipedia：

% 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之間的差異不超過v_quadratic_error的值時，while循環結束。

這裏有更多的解釋。首先，請注意M_hat是一個矩陣，而v是一個向量。 while循環替換v產品M_hat * v（歸一化爲單位向量）。當由於一次迭代而在v中的更改足夠小時，循環結束。這就是「融合」在這種情況下的含義。

這似乎是標準power iteration循環找到對應於矩陣的主要特徵值（在這種情況下爲M_hat）的特徵向量。不知道更多關於整體算法（我不打算研究），我不能說爲什麼這個計算是有用的。