Desde hace unos años, Google se ha convertido en el buscador estándar en la red. Uno de sus secretos es el algoritmo PageRank, que combina la teoría espectral de grafos con álgebra lineal.
Un poco de historia
Google fue creado en 1998 por Sergei Brin y Lawrence Page en la Universidad de Stanford. El nombre es una variación sobre el término googol, es decir, el número 10100, haciendo referencia al gran volumen de datos con el que el programa tiene que trabajar. Según la página de Google, atiende a más de 250 millones de consultas diarias. El problema con todos estos datos es el siguiente: ¿en qué orden mostramos estos datos? ¿Cúales son los resultados más interesantes para el público? Necesitamos cierto orden de asignación de búsqueda.
Hoy por hoy, Google utiliza dos criterios de búsqueda básicos. El formato de la palabra buscada en las distintas webs, dependiendo de como de importancia se le de a esta palabra. Si se buscan varias palabras, se da prioridad a las entradas en las que las palabras aparezcan más cerca.
Modelo de ordenación de Google
Sean Pi las páginas web y Xi la importancia:
Paso 1:
Primer paso. Con un grafo orientado o dirigido G. Cada sitio de la red es un vértice, y hay una arista entre P_i y P_j si desde la página Pi hay un enlace a la página Pj . Construimos la traspuesta de la matriz de adyacencia, es decir, la matriz M = (mij) donde mij es el número de enlaces que van de Pj a Pi (si no hay enlaces de Pj a Pi entonces mij = 0 y supondremos que una página siempre se enlaza a sí misma, por lo que los elementos diagonales valen 1).
Paso 2:
La importancia de una página Pi será mayor en función de dos factores: que sea probable llegar a Pi desde otras páginas (como enlaces externos) y que las citas a Pi sean de páginas con gran importancia. El modelo asigna un valor de importancia xi a una página (vértice) Pi en función de lo probable que sea llegar a ella. Se considera que una parte de esta probabilidad es uniforme (todas las páginas tendrían la misma probabilidad de ser visitadas aleatoriamente). Esta sería 1/N, siendo N el número de páginas en Internet. La otra parte de esta probabilidad se considera proporcional a la suma de las importancias de los vértices de los que salen aristas confluyentes en Pi o, lo que es lo mismo, de las páginas que enlazan con Pi. La proporcionalidad vendrá dada en función de los enlaces que salgan de cada página. La importancia de la página Pi se expresará mediante ∑(mij/kj)*xj; donde kj es el número de enlaces que salen de la página Pj . Esta expresión es la coordenada i–ésima del vector M’x , donde M’ es la matriz que tiene por elementos mij’=mij/kj. Al dividir por kj estamos ponderando el hecho de que no es lo mismo estar enlazado desde una página selectiva que solo tiene un enlace que estarlo desde una página promiscua que tiene muchos. Cabe destacar que todos los mij/kj suman 1. La importancia de una página Pi se define como Xi = (1‑d)/N + d*∑(mij/kj)*xj, para algún d entre 0 y 1.
Conclusión
Vectorialmente, tenemos la igualdad x = (((1‑d)//N)*1N +d*M’)*x, donde 1N es una matriz de NxN donde todos sus elementos son 1.
Resumiendo, el algoritmo PageRank busca un vector xi en la matriz A= ((1‑d)/N)*1N d*M’.
