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 matriui 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:
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
eigenPlot.gif

El mètode de la potència: valor propi de mòdul màxim

La forma més simple de calcular un vector propi és el mètode de la potència, que consisteix en aplicar la iteració:
essent A una matriu lineal i normalitzant a cada pas el vector obtingut.
Aquest mètode ens proporciona el vector propi corresponent al valor propi de mòdul màxim (dominant). La convergència està garantida sempre que existeixi un valor propi més gran que la resta .
El valor propi es calcula a partir del quocient entre les coordenades d'un vector i el seu transformat.
Per veure el seu funcionament, ho compararem amb un exemple senzill amb el que ens dona el Matlab.
format short
A=[1, 3; 4, 2]/4;
[veps, vaps]=eig(A) %funció que calcula els veps i vaps amb Matlab
veps = 2×2
-0.7071 -0.6000 0.7071 -0.8000
vaps = 2×2
-0.5000 0 0 1.2500
x = [1;1]; %vector inicial (podria ser qualsevol) en el que comencem les iteracions
xant = x/norm(x); %normalitzem la direcció
tol = 1.e-6; %valor per aturar les iteracions
variacio = 1000; %valor suficientment gran
nIter=0;
while (variacio > tol && nIter < 100 ) %fa un màxim de 100 iteracions
nIter = nIter+1;
xnou = A*xant;
xnou = xnou/norm(xnou);
variacio = max(abs(xnou-xant)); %norma subinfinit (equivalent: norm(xnou-xant,inf))
% actualitzem per passar a la propera iteració
xant = xnou;
end
 
eigMax = max((A*xnou)./xnou); %ha de donar pràcticament el mateix per a totes les components
fprintf('nIter = %d , vap max = %f, vep=[%.4e, %.4e] \n',nIter,eigMax,xnou); %noteu el canvi de signe del vector
nIter = 15 , vap max = 1.250000, vep=[6.0000e-01, 8.0000e-01]

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

L’algorisme de PageRank va ser inventat per Page i Brin (1998) i es va utilitzar en el prototip del motor de cerca de Google.
L 'objectiu és estimar la popularitat, o la importància, d' una pàgina basada en la interconnexió de la web. La idea que hi ha al darrere és
La idea de la classificació que fa Google en la cerca de les pàgines més rellevants quan fem una consulta, es basa en l'estudi de la matriu de connectivitat entre les diferents pàgines. Aquesta connectivitat es quantifica a partir dels links entre les pàgines. Així, per exemple, podem tenir un conjunt de pàgines relacionades entre si pel graf de la figura (on cada fletxa significa un link d'una a l'altra).
Si numerem els diferents nodes del graf com A=1, B=2, C=3, D=4. Cada connexió la representem com un coefficient en la matriu de connectivitat, en la que cada fila és la informació de quins nodes linken al de la fila actual. Les files signifiquen fletxes que entren i les columnes les que surten de cada node.
C1 = [0,0,1,1;
1,0,0,0;
1,0,0,1;
1,1,1,0]
C1 = 4×4
0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0
Normalització:
En aquesta matriu cada columna indica les fletxes que 'surten' de cada node, per tant normalitzarem per columnes per representar de forma normalitzada el pes de la connectivitat de cada node. Tècnicament es diu que la matriu és estocàstica per columnes. La matriu obtinguda satisfà que la suma per columnes és 1.
for i=1:size(C1,2)
A1(:,i) = C1(:,i)/sum(C1(:,i));
end
A1
A1 = 4×4
0 0 0.5000 0.5000 0.3333 0 0 0 0.3333 0 0 0.5000 0.3333 1.0000 0.5000 0
Algoritme iteratiu:
Essencialment consisteix en aplicar la matriu A de forma successiva a un vector inicial que normalment és el vector ones. De fet, es tracta del mètode de la potència com hem vist anteriorment. Aquí el vector propi associat al valor propi dominant tindrà una interpretació fonamental a nivell de components ja que la màxima component correspon al node de major importància del graf.
A=[];
A=A1; %matriu d'iteració
tol = 1.e-3;
x=ones(size(A,1),1);
x = x/norm(x); %normalitzem la direcció
X=[0,x'];
xnou=A*x;
variacio = max(abs(xnou-x));
nIter=1;
X=[X;nIter,xnou'];
while (variacio > tol && nIter < 100 )
nIter=nIter+1;
x=xnou;
xnou=A*x;
X=[X; nIter,xnou'];
variacio = max(abs(xnou-x));
end
X
X = 11×5
0 0.5000 0.5000 0.5000 0.5000 1.0000 0.5000 0.1667 0.4167 0.9167 2.0000 0.6667 0.1667 0.6250 0.5417 3.0000 0.5833 0.2222 0.4931 0.7014 4.0000 0.5972 0.1944 0.5451 0.6632 5.0000 0.6042 0.1991 0.5307 0.6661 6.0000 0.5984 0.2014 0.5344 0.6658 7.0000 0.6001 0.1995 0.5324 0.6681 8.0000 0.6002 0.2000 0.5341 0.6657 9.0000 0.5999 0.2001 0.5329 0.6671
[val,highestRank]=max(X(end,2:end)); %valor màxim de la última iteració
fprintf('valor =%f, numero de pàgina = %d \n',val, highestRank);
valor =0.666484, numero de pàgina = 4

Un cas especial: una pàgina no cita cap altra (dangling node)

Considerem ara el cas de la figura, en el que el node D no te cap fletxa de sortida (no cita cap pàgina). Aquest cas no permet l'aplicació de l'algorisme i haurem de modificar la matriu de connectivitat.
Per aquest cas la matriu de connectivitat és:
C2=[0, 0, 1, 0;
1, 0, 0, 0;
1, 0, 0, 0;
1, 1, 1, 0];
% que normalitzada seria:
for i=1:size(C2,2)
A2(:,i) = C2(:,i)/sum(C2(:,i));
end
A2
A2 = 4×4
0 0 0.5000 NaN 0.3333 0 0 NaN 0.3333 0 0 NaN 0.3333 1.0000 0.5000 NaN
per descomptat aquesta matriu no es podria utilitzar per iterar. Tot i que respectéssim la última columna de zeros, amb la qual cosa es podrien fer les iteracions, llavors la convergència seria cap a zero (feu el càlcul).
Per arreglar el problema substituim la columna de NaN per un valor equirrepartit com seria 1/N on N és el número de nodes.
N=size(A2,2);
A2(:,4)=1/N;
A2
A2 = 4×4
0 0 0.5000 0.2500 0.3333 0 0 0.2500 0.3333 0 0 0.2500 0.3333 1.0000 0.5000 0.2500
Ara ja podem fer les iteracions:
A=[];
A=A2; %matriu d'iteració
tol = 1.e-3;
x=ones(size(A,1),1);
x = x/norm(x); %normalitzem la direcció
X=[0,x'];
xnou=A*x;
variacio = max(abs(xnou-x));
nIter=1;
X=[X;nIter,xnou'];
while (variacio > tol && nIter < 100 )
nIter=nIter+1;
x=xnou;
xnou=A*x;
X=[X; nIter,xnou'];
variacio = max(abs(xnou-x));
end
X
X = 11×5
0 0.5000 0.5000 0.5000 0.5000 1.0000 0.3750 0.2917 0.2917 1.0417 2.0000 0.4062 0.3854 0.3854 0.8229 3.0000 0.3984 0.3411 0.3411 0.9193 4.0000 0.4004 0.3626 0.3626 0.8743 5.0000 0.3999 0.3521 0.3521 0.8960 6.0000 0.4000 0.3573 0.3573 0.8854 7.0000 0.4000 0.3547 0.3547 0.8906 8.0000 0.4000 0.3560 0.3560 0.8880 9.0000 0.4000 0.3553 0.3553 0.8893
[val,highestRank]=max(X(end,2:end)); %valor màxim de la última iteració
fprintf('valor =%f, numero de pàgina = %d \n',val, highestRank);
valor =0.888672, numero de pàgina = 4

Xarxes separables

Un problema diferent és quan les connexions estàn definides de manera que hi ha blocks a la xarxa dels quals no podries sortir (seguint només els enllaços)
Això és el que passa amb els blocks E,F,G,H de la xarxa de la figura
C3=[0,0,1,0,0,0,0,0;
1,0,0,1,0,0,0,0;
1,0,0,0,0,0,0,0;
1,1,1,0,0,0,0,0;
0,1,0,0,0,1,0,0;
0,0,0,0,0,0,1,1;
0,0,0,1,1,0,0,1;
0,0,0,0,0,1,0,0;];
for i=1:size(C3,2)
A3(:,i) = C3(:,i)/sum(C3(:,i));
end

Graph irreduibles: el número màgic de Google

El cas anterior és el d'un graf reduible, de fet un graf es diu que és irreduible si podem sortir d'un node i anant seguint les fletxes, puc arribar a qualsevol altre node i viceversa.
Si fem les iteracions per un graf reduible, tendiran a zero. Per arreglar el problema s'ha de modificar la matriu normalitzada amb la fórmula:
on d és una constant (damping factor), i N el número de columnes de A.
Google va utilitzar el valor de damping d=0.85
d= 0.85;
N=size(A3,2);
M=d*A3+((1-d)/N)*ones(size(A3));
%
% ara podem fer les iteracions com en els casos anteriors:
%
A=[];
A=M; %matriu d'iteració
tol = 1.e-3;
x=ones(size(A,1),1);
x = x/norm(x); %normalitzem la direcció
X=[0,x'];
xnou=A*x;
variacio = max(abs(xnou-x));
nIter=1;
X=[X;nIter,xnou'];
while (variacio > tol && nIter < 100 )
nIter=nIter+1;
x=xnou;
xnou=A*x;
X=[X; nIter,xnou'];
variacio = max(abs(xnou-x));
end
[val,highestRank]=max(X(end,2:end)); %component màxima de la última iteració
fprintf('valor =%f, numero de pàgina = %d \n',val, highestRank);
valor =0.802451, numero de pàgina = 6

Matrius estocàstiques: valors propis associats

La convergència de les iteracions va lligada als valors propis de la matriu d'iteració. Per construcció les matrius que hem fet servir s'anomenen matrius estocàstiques per columnes (la suma per columnes és 1) i tots els seus elements són positius. El teorema de Perron-Frobenius garanteix que aquestes matrius tenen un valor propi de mòdul 1 i els altres són de mòdul estrictament menor que 1.
Veiem-ho en les nostres matrius:
disp('Mòdul Vaps A1:');
Mòdul Vaps A1:
abs(eig(A1)) %abs és el mòdul si el vap és complexe
ans = 4×1
1.0000 0.4082 0.4082 0.5000
disp('Mòdul Vaps A2:');
Mòdul Vaps A2:
abs(eig(A2))
ans = 4×1
1.0000 0.5000 0.2500 0.0000
disp('Mòdul Vaps M:');
Mòdul Vaps M:
abs(eig(M))
ans = 8×1
1.0000 0.7361 0.7361 0.4250 0.3470 0.4250 0.3470 0.0000

Exemple amb N gran: Generació d'un graf aleatori

Podem generar grafs de mida més gran en forma aleatòria (si no tenim dades) a partir d'una matriu C generada amb 0 i 1's.
rng(2022); %fix the seed to obtain the same random numbers
N = 40;
C4 = round(rand(N)); %omplim la matriu de 0 i 1
for i = 1:N
C4(i,i) = 0;
end
spy(C4)
% normalització
for i = 1:size(C4,2)
A4(:,i) = C4(:,i)/sum(C4(:,i));
end
% mirem si hi ha alguna columna de NaN
A4(isnan(A4)) = 1/N;
% evitem grafs irreduibles
d= 0.85;
M4 = d*A4+((1-d)/N)*ones(size(A4));
%
% ara podem fer les iteracions com en els casos anteriors:
%
A = [];
A = M4; %matriu d'iteració
tol = 1.e-3;
x = ones(size(A,1),1);
x = x/norm(x); %normalitzem la direcció
X = [0,x'];
xnou = A*x;
variacio = max(abs(xnou-x));
nIter = 1;
X = [X;nIter,xnou'];
while (variacio > tol && nIter < 100 )
nIter = nIter+1;
x = xnou;
xnou = A*x;
X = [X; nIter,xnou'];
variacio = max(abs(xnou-x));
end
[val,highestRank] = max(X(end,2:end)); %valor màxim de la última iteració
fprintf('valor =%f, numero de pàgina = %d \n',val, highestRank);
valor =0.199439, numero de pàgina = 35
disp('Mòdul Vaps M4: (els 8 primers)');
Mòdul Vaps M4: (els 8 primers)
modVaps = abs(eig(M4));
modVaps(1:8) %mostrem només els 8 primers vaps en mòdul
ans = 8×1
1.0000 0.1592 0.1462 0.1462 0.1433 0.1433 0.1386 0.1386
Exercici 1:
La figura de sota es correspon a la representació d'una esfera (una pilota de futbol) o també d'un graf bidireccional de 60 nodes (àtoms de carbó) i 90 arestes de connexions conegut en Química amb el nom de fullereno C-60 (Bucky) i la seva numeració dins el Matlab.
La seva matriu de connectivitat o adjacencies es pot carregar des de Matlab fent
C=bucky;
(a) Apliqueu el mètode del GoogleRank amb i per classificar els nodes més importants
(b) Introduïu una nova connexió del node 10 al 50 i apliqueu el mateix algoritme.
(c) Feu el el mateix però a partir del model original i eliminant les dues connexions entre els node 7 i 30.
function vectarrow (X,DX,tmny,clr,lw)
% Dibuixa una fletxa en el punt X amb direcció DX de mida tmny, color clr i gruix lw
% (c) Rafael Ramirez 2019
%
nrm = norm(DX);
 
if (nrm > 1.e-5)
DX=tmny*DX/nrm;
x0 = X(1);
y0 = X(2);
x1 = X(1)+DX(1);
y1 = X(2)+DX(2);
plot([x0;x1],[y0;y1],clr,'LineWidth',lw);
alpha = 1; % Tamaño de la cabeza (alpha pequeña = flecha invisible)
beta = 0.5; % Tamaño de la base (beta pequeña = flecha puntiaguda)
hu = [x1-alpha*(DX(1)+beta*DX(2)); x1; x1-alpha*(DX(1)-beta*DX(2))];
hv = [y1-alpha*(DX(2)-beta*DX(1)); y1; y1-alpha*(DX(2)+beta*DX(1))];
plot(hu(:),hv(:),clr,'LineWidth',lw) % Plot arrow head
end
 
end
 
(c) Numerical Factory 2022 (following the paper http://home.ie.cuhk.edu.hk/~wkshum/papers/pagerank.pdf)