Pagerank [Tarea extra]

¿Qué es PageRank?

PageRank o PR, es un algoritmo para analizar las conexiones simultáneas que existen sobre un sistema de clasificación de páginas Web, el cual es utilizado como el motor de búsqueda de Google, para así poder medir cuantitativamente la popularidad de una página web y clasificar los resultados de la búsqueda.

Podemos decir, que los nodos que tenemos en el siguiente grafo son los estados de las páginas web y que suponiendo que cada nodo tiene k ligas que salen de estas, tenemos que la probabilidad de transición de una página a otra, va a ser de 1/k para cada uno, esto sería como cuando una persona solamente navega dando clicks al azar, solamente siguiendo de una página a otra.

Si suponemos que todas las páginas web estan conectadas entre ellos, nos proporciona una probabilidad de que cada cierto tiempo que nosotros llegamos a ésa página, esto quiere decir que, el pagerank nos dice que tan fácil es llegar a esta página, por lo que si ésta es importante, muchas otras páginas van a estar apuntando a ti, entonces si una persona navega al azar, frecuentemente va a llegar a una página que esta apuntado a ti y con esta mayor probabilidad, va a llegar a ver ésa página importante.

Ejemplo:

Para hacer este procedimiento, he dibujado un grafo simulando una mini red de 10 páginas, las cuales están todas conectadas entre si, pero algunas tienen mas ligas que otras, en este caso, podemos ver que las que están en rojo solamente tienen una liga a ellas, las amarillas tienen dos ligas y la verde es la que tiene mas ligas en la red, por lo tanto es la que se considera más importante.

Dibujo grafo

Representación gráfica

Aquí podemos ver la matriz de adyacencia, que es la que dice si hay o no liga, si tenemos un 1 quiere decir que esta tiene liga con la coordenada correspondiente, si tiene un 0 no tiene liga, haciendo una matriz binaria, luego para poder obtener el pagerank, tenemos que convertir esta matriz de adyacencia en una matriz estocástica, según sus transciones, por lo que cada uno sumará un total de k ligas y dividimos entre cada uno de estos elementos para obtener que la suma sea un uno y sea estocástica, luego con esto sacamos el eigenvector valor izquierdo, obteniendo el vector que nos va a decir cuales son las páginas más importantes.

Luego de esto, vemos que los valores grandes son los más importantes, para luego ligar este  que en su caso es página 2, que comparado con otras, tiene que ser mayor.

Obtenemos como resultado en el vector, la importancia de cada una de las páginas, en donde tenemos por muy superior a la página 2.

Por medio del comando spy, podemos obtener una gráfica sobre como está la matriz y cuales son sus ligas.

Referencias.
¿Qué es un eigenvector?
¿Qué es pagerank?
Algoritmo de pagerank
Octave