0

wikipediaに Google の 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 の目的を理解できます。ウィキペディアにも記事のアルゴリズム仕様にも記載されていません。

4

1 に答える 1

1

収束テストのようです。との間whileの L 2の差が の値を超えない場合、ループは終了します。vlast_vv_quadratic_error

もう少し説明があります。M_hatまず、は行列であり、 はベクトルであることに注意してくださいv。whileループはv積に置き換えられます(M_hat * v単位ベクトルに正規化されます)。v1 回の反復による変化が十分に小さくなると、ループは終了します。これが、このコンテキストでの「収束」の意味です。

これは、行列の優勢な固有値に対応する固有ベクトルを見つけるための標準的な累乗反復M_hatループのようです (この場合は)。全体的なアルゴリズム (私は調査するつもりはありません) について詳しく知らなければ、この計算がなぜ有用なのかはわかりません。

于 2012-12-20T03:09:03.940 に答える