Matrices de transición y clasificación de páginas web
Grafos dirigidos (o dígrafos)
Los grafos dirigidos son representaciones de relaciones entre elementos de un conjunto. En el caso que nos ocupa (páginas web), un grafo dirigido representa los enlaces (links) entre páginas. Las relaciones entre los elementos de un grafo tienen dirección, de modo que si existe un enlace de la página A a la B, el grafo mostrará una flecha de A hacia B.
En la figura se muestra el grafo de 4 páginas web (cada una representada mediante un número)
Matriz de adyacencia
Un grafo dirigido está biunívocamente relacionado con su matriz de adyacencia (o de conectividad). Los elementos de dicha matriz son 0 ó 1 de manera que el elemento 
de la matriz de adyacencia será 1 si existe un enlace de la página j a la página i. De modo que la matriz de adyacencia del grafo anterior es:
de la matriz de adyacencia será 1 si existe un enlace de la página j a la página i. De modo que la matriz de adyacencia del grafo anterior es:A=[0 1 1 1;1 0 1 1;1 1 0 1;0 1 0 0]
Matriz de probabilidad de transición
La matriz de transición de una matriz de adyacencia es la matriz obtenida dividiendo cada elemento de A por la suma de los elementos de la columna correspondiente.
En el ejemplo anterior, calculamos la matriz de transición mediante los comandos de Matlab (recordar que el comando "sum" de Matlab suma las columnas de una matriz y que el comando "./" divide dos arrays (matrices o v, por taectores( elemento a elemento, para calcular la matriz de probabilidad de transición (B) bastará:
B=A./(sum(A))
Vector de estado
Si navegamos a través de las páginas de una web, el vector de estado 
es un vector columna cuyo elemento i-ésimo es la probabilidad de que estemos en la página i después de k “clicks”.
es un vector columna cuyo elemento i-ésimo es la probabilidad de que estemos en la página i después de k “clicks”.Supongamos, en el ejemplo anterior que salimos desde la página 2, en ese caso el vector de estado inicial será:
x0=[0;1;0;0]
Por tanto, si queremos conocer cuáles son las probabilidades de estar en otra página partiendo de la página 2, bastará multiplicar la matriz de probabilidad de transición por el vector de estado:
x1=B*x0
Vemos que existe 1/3 de probabilidad de saltar a las páginas 1, 3 y 4 y 0 de permanecer en la página 2 (ya que no existe un enlace de la página 2 a ella misma en el grafo).
Si siguiéramos navegando por las 4 páginas web del grafo iríamos obteniendo distintos vectores de estado con las probabilidades de encontrarnos en cada página después de k clicks (o saltos). Repitiendo este proceso observamos que el vector de estado tiende a un valor. Veremos a continuación cómo calcularlo mediante un bucle for:
x=x0;
E=x0;
for i=1:1:14
x0=B*x0;
E=[E x0];
i=i+1;
end
E
Si observamos los distintos vectores de estado obtenidos (acumulados en las columnas de la matriz E) vemos que a partir de la columna 11 (es decir, en el vector de estado 
) el vector no cambia. Existe, por tanto, un vector estacionario 
tal que 
. O lo que es lo mismo, el vector estacionario es un vector propio de la matriz de probabilidad de transición asociado al autovalor 
.
) el vector no cambia. Existe, por tanto, un vector estacionario tal que . O lo que es lo mismo, el vector estacionario es un vector propio de la matriz de probabilidad de transición asociado al autovalor . Se puede demostrar que este vector estacionario no depende de la página desde la que comencemos.
Esto nos permite "ordenar" por importancia las páginas web. En nuestro caso, si extraemos la columna 11 de la matriz E obtendremos el vector estacionario:
xs=E(:,11)
Observamos que el orden importancia de las páginas es (aunque las páginas 1 y 3 muestran las mismas probabilidades, Matlab tomará el mayor número de decimales). Para clasificar las páginas debemos "reordenar" de mayor a menor los elementos del vector conservando su ínidice (número de página web a la que corresponde). Lo logramos mediante dos bucles "for" anidados tal como se muestra a continuación:
conservando su ínidice (número de página web a la que corresponde). Lo logramos mediante dos bucles "for" anidados tal como se muestra a continuación:url = {'web 1', 'web 2', 'web 3','web 4'};
idx=1:4;
for k=1:3
indm=k;
for j=k+1:4
if xs(idx(j))>xs(idx(indm))
indm=j;
end
end
temp=idx(k);
idx(k)=idx(indm);
idx(indm)=temp;
end
for i=1:4
text = [num2str(i), 'º será la url: ', url{idx(i)}, '.'];
disp(text)
end
Saltos entre páginas no enlazadas
Sin embargo, la realidad es que existe una probabilidad de que quien esté navegando entre webs salte a otra no enlazada. Eso se representa mediante un factor de atenuación 
que modifica la matriz de probabillidad de transición de modo que los elementos de la nueva matriz (M) serán: 
(siendo n el número de páginas del grafo).
que modifica la matriz de probabillidad de transición de modo que los elementos de la nueva matriz (M) serán: (siendo n el número de páginas del grafo).Matricialmente, el vector de estado k-ésimo se expresa mediante:
Así en nuestro ejemplo anterior, si tomamos un factor de atenuación de 
y volvemos a calcular los sucesivos vectores de estado obtendremos:
y volvemos a calcular los sucesivos vectores de estado obtendremos:delta=0.85;
M=delta*B+(((1-delta)/4)*ones(4))
De la misma manera que sucedía con la matriz de probabilidad de transición B, la matriz M tiene un autovector estacionario que se corresponde con el autovalor 1 (autovalor dominante o de mayor módulo). Podemos encontrarlo mediante el comando "eig" de Matlab (ver el menú de ayuda de Matlab para entender cómo opera esta función).
[~, D] = eig(M);
fprintf('El autovalor dominante de M es %f\n',D(1,1))
El vector correspondiente al autovalor 1 será el vector estacionario que nos permitirá clasificar las páginas de nuevo (esta vez con el factor de atenuación). Para calcularlo basta aplicar la teoría de autovalores y autovectores:
I=eye(4);
xs1=null(I-M);
xs1=xs1./sum(xs1)
Observa que hemos tenido que "normalizar" el vector resultante xs1 dividiendo cada una de sus componentes por la suma de ellas.
Dibujo de grafos con Matlab
Para dibujar grafos dirigidos con Matlab debemos emplear el comando "digraph". Para ello, debemos tener en cuenta que las matrices de transición en Matlab son la traspuesta de la que hemos calculado nosotros.
G=digraph(A',{'web 1','web 2','web 3','web 4'});
plot (G)
Cálculo de vectores estacionarios con Matlab
Matlab posee una función interna que permite calcular el vector estacionario a partir de una grafo dirigido y un factor de atenuación mediante el comando "centrality":
xsol=centrality(G,'pagerank','FollowProbability',0.85)