Metode PageRank

image from google

Jika matriks $\ Mathcal {M}$ probabilitas transisi, yaitu, kolom-kolom stochastic tanpa terdiri dari hanya nol dan $\ Mathbf {R}$ merupakan distribusi probabilitas (yaitu, $| \ Mathbf {R} | = 1$ , $\ Mathbf {E} \ mathbf {R} = \ mathbf {1}$ di mana $\ Mathbf {E}$ adalah matriks yang semua), Persamaan. (**) Setara dengan

$\ Mathbf {R} = \ left (d \ mathcal {M} + \ frac {1-d} {N} \ mathbf {E} \ right) \ mathbf {R} =: \ widehat {\ mathcal {M}} \ mathbf {R}$ . (***)

Oleh karena itu PageRank $\ Mathbf {R}$ adalah vektor eigen utama $\ Widehat {\ mathcal {M}}$ . Sebuah cara yang mudah dan cepat untuk menghitung ini menggunakan metode listrik : dimulai dengan vektor sewenang-wenang x (0)

, operator $\ Widehat {\ mathcal {M}}$ diterapkan berturut-turut, yaitu,

$x (t + 1) = \ widehat {\ mathcal {M}} x (t)$ .

sampai sampai

$| X (t + 1) - x (t) | <\ epsilon$ .

Perhatikan bahwa dalam Pers. (***) Matriks di sisi kanan dalam kurung dapat diartikan sebagai

$\ Frac {1-d} {N} \ mathbf {E} = (1-d) \ mathbf {P} \ mathbf {1} ^ t$ .

di mana $\ Mathbf {P}$ adalah distribusi probabilitas awal. Dalam kasus saat ini

$\ Mathbf {P}: = \ frac {1} {N} \ mathbf {1}$ .

Akhirnya, jika $\ Mathcal {M}$ memiliki kolom dengan hanya nilai nol, mereka harus diganti dengan vektor probabilitas awal $\ Mathbf {P}$ . Dengan kata lain

$\ Mathcal {M} ^ \ prime: = \ mathcal {M} + \ mathcal {D}$ .

di mana matriks $\ Mathcal {D}$ didefinisikan sebagai

$\ Mathcal {D}: = \ mathbf {P} \ mathbf {D} ^ t$ .

dengan

$\ Mathbf {D} _i = \ begin {} 1 kasus, dan \ mbox {jika} L (p_i) = 0 \ \\ 0, & \ mbox {jika} \ end {} kasus$

Dalam hal ini, di atas dua perhitungan menggunakan $\ Mathcal {M}$ hanya memberikan PageRank sama jika hasilnya dinormalisasi:

$\ Mathbf {R} _ {\ textrm {daya}} = \ frac {\ mathbf {R} _ {\ textrm {berulang}}} {| \ mathbf {R} _ {\ textrm {berulang}} |} = \ frac {\ mathbf {R} _ {\ textrm {aljabar}}} {| \ mathbf {R} _ {\ textrm {aljabar}} |}$ .

PageRank MATLAB / Octave pelaksanaan

Parameter% M adjacency matrix mana M_i, j merupakan link dari 'j' ke 'i', sehingga untuk semua 'j' sum (i, M_i, j) = 1 
% Parameter d faktor redaman 
Parameter% v_quadratic_error kesalahan kuadrat untuk v 
Kembali% v, vektor jajaran sehingga v_i adalah ke-i rank dari [0, 1]
 
Fungsi   v  =  M, d, v_quadratic_error 
 
N = ukuran  M,  ; % N sama dengan setengah ukuran M 
v =  N,  ;
v = v ./ norma  v,  ;
last_v = orang  N,  *  ;
M_hat =  . d * M  +  - d  / N  *.  N, N  ;
 
sementara norma  v - last_v,  > v_quadratic_error 
 last_v = v;
 v = M_hat * v;
 v = v ./ norma  v,  ;
 
 
endfunction
 
Fungsi   v  = rank2  M, d, v_quadratic_error 
 
N = ukuran  M,  ; % N sama dengan setengah ukuran M 
v =  N,  ;
v = v ./ norma  v,  ;    % ini sekarang L1, L2 tidak 
last_v =  N,  *  ;
M_hat =  . d * M  +  - d  / N  *.  N, N  ;
 
sementara norma  v - last_v,  > v_quadratic_error 
 last_v = v;
 v = M_hat * v;
        % Dihapus L2 norma PR iterasi 
akhir
 
endfunction

Contoh kode memanggil fungsi rank didefinisikan di atas:

M =      ;      ;      ;      ;      ;
  M,  , 0,001

Contoh ini membutuhkan 13 iterasi untuk berkumpul.

Berikut ini adalah bukti bahwa rank.m tidak benar. Hal ini didasarkan pada contoh grafis pertama. Pemahaman saya adalah bahwa rank.m menggunakan norma yang salah pada input, kemudian terus renormalize L2, yang tidak perlu.

% Ini merupakan contoh grafik, benar normal dan akuntansi untuk tenggelam (Node A) 
% dengan memungkinkan untuk secara efektif transisi acak 100% dari waktu, termasuk untuk dirinya sendiri. 
Sementara% RANK.m tidak benar-benar menangani hal ini tidak benar, itu tidak menunjukkan secara tepat bagaimana seharusnya 
% menangani node sink (satu solusi yang mungkin akan menjadi DIRI TRANSISI 1,0), yang tidak 
% memberikan hasil yang benar.
 
test_graph = 
  0.09091    0.00000    0.00000    0.50000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    1.00000    0.50000    0.33333    0.50000    0.50000    0.50000    0.50000    0.00000    0.00000 ;
    0.09091    1.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.33333    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.50000    0.50000    0.50000    0.50000    1.00000    1.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.33333    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000 ;
    0.09091    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000    0.00000  
 
pr =  test_graph,  , 0,001    % SALAH tidak normal.
 
% 0.062247 
% 0.730223 
% 0.650829 
% 0.074220 
% 0.153590 
% 0.074220 
% 0.030703 
% 0.030703 
% 0.030703 
% 0.030703 
% 0.030703
 
pr / norma  pr,     % BENAR sekali normal. Saya masih tidak tahu mengapa normalisasi L2 terjadi (v = v / norma (v, 2))
 
% 0.032781 
% 0.384561 
% 0.342750 
% 0.039087 
% 0.080886 
% 0.039087 
% 0.016170 
% 0.016170 
% 0.016170 
% 0.016170 
% 0.016170
 
pr = rank2  test_graph,  , 0,001  % BENAR, hanya membutuhkan masukan PR normalisasi (pastikan merangkum 1,0)
 
% 0.032781 
% 0.384561 
% 0.342750 
% 0.039087 
% 0.080886 
% 0.039087 
% 0.016170 
% 0.016170 
% 0.016170 
% 0.016170 
% 0.016170

Metode PageRank

Related : Metode PageRank

Popular Posts

Labels

Total Tayangan Laman

Arsip