Google의 PageRank 알고리즘에서 quadratic_error 변수의 역할은 무엇입니까? quadratic_error가 무엇을 알아낼 :

Question

은 '

% 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 

내가 할 수 wikipedia에 페이지 랭크 (PageRank)'구글의 구현이있다. 그것은 위키피디아와 기사의 알고리즘 스펙에 설명되어 있지 않습니다.

Answer 1

마치 수렴 테스트 인 것 같습니다. while 루프는 L 의 차이가 v과 last_v 사이가 v_quadratic_error이 아닐 때 끝납니다.

여기에 대한 설명이 나와 있습니다. 먼저, M_hat은 행렬이고 v은 벡터입니다. while 루프는 v을 M_hat * v (단위 벡터로 정규화) 제품으로 바꿉니다. 한 번의 반복으로 인해 v의 변경 사항이 충분히 작 으면 루프가 종료됩니다. 이것이 컨버전스가이 문맥에서 의미하는 것입니다.

이것은 매트릭스의 우세한 고유 값 (이 경우 M_hat)에 해당하는 고유 벡터를 찾기위한 표준 power iteration 루프 인 것으로 보입니다. 전체 알고리즘 (내가 조사하지 않을 것임)에 대해 더 많이 알지 못하면이 계산이 왜 유용한 지 말할 수 없습니다.