Aplicació del càlcul de Valors i Vectors Propis: Page Rank

Índex

Vectors i valors propis: idea intuïtiva Exemple en 2D El mètode de la potència: valor propi de mòdul màxim PageRank: Aplicació del càlcul de Valors i Vectors Propis Un cas especial: una pàgina no cita cap altra (dangling node) Xarxes separables Graph irreduibles: el número màgic de Google Matrius estocàstiques: valors propis associats Exemple amb N gran: Generació d'un graf aleatori

Vectors i valors propis: idea intuïtiva

Els vectors propis són aquells que mantenen la direcció després de ser multiplicats per una matriu. Tot i mantenir la direcció, la seva llargada i el seu sentit pot variar. Això depèn del factor que multiplica la direcció i que s'anomena valor propi. La nomenclatura usual és

, on λ és el valor propi i v el vector propi.

Exemple en 2D

Prenem la matriu

i per visualitzar els seus vaps i veps, pintarem en blau el vector original i en verd la seva imatge perA. Per visualitzar-ho en

, podem agafar els vectors unitaris v ( en blau) amb la punta sobre la circumferència de radi 1 i pintem els seus transformats

pel producte amb la matriuA (en verd). Com veurem els originals es mouen sobre una circumferència i els transformats es mouen sobre una el·lipse. Noteu que quan les dues direccions estan alineades estem davant d'una direcció pròpia. El que podem observar és que:

Si v i tenen mateix sentit, el vap associat λ és positiu
Si v i tenen sentit oposat, el vap associat λ és negatiu
Si , el vap associat
Si , el vap associat

A = [1, 3; 4, 2]/4;
h = 2*pi/200;
ang = 0:h:2*pi; % dividim tot el cercle en angles 
v = [cos(ang); sin(ang)]; %tots els vectors inicials de norma 1
vt = A*v; %tots els vectors transformats per A
% pintem cada vector i el seu transformat
for k = 1:2 %fem dues voltes
    for i = 1:size(v,2)
        plot(v(1,:), v(2,:),'b'); % el cercle
        hold on;
        plot(vt(1,:), vt(2,:),'g'); % l'el·lipse
        axis equal
        plot([0,v(1,i)],[0,v(2,i)],'b');
        plot([0,vt(1,i)],[0,vt(2,i)],'g');
        vv = 0.95*[v(1,i),v(2,i)];
        vvt = 0.95*[vt(1,i),vt(2,i)];
        vectarrow (vv,vv,0.04,'b',2)
        vectarrow (vvt,vvt,0.04,'g',2)
        hold off;
        pause(0.01) %en segons
    end
end