La fórmula de Google

El Page Rank, la patente más famosa de Google, buscador de  Larry y Sergei, es una de las principales ventajas competitivas que permitió a esta compañía aplastar a sus competidores en el campo de las búsquedas en internet y hacerse el gigante que son hoy.

El Page Rank, como todos la conocemos, es una idea genial para hallar el valor o "importancia" que tiene una página web determinada. Esta "importancia" se emplea después para mostrar unas páginas de manera preferente cuando realizamos una búsqueda en Google.

1. La "importancia" de una página web sólo depende de las páginas web que la enlazan.

Si tienes una página web y esta es enlazada desde páginas importantes (de alto Page Rank) tú recibirás una parte de esa “importancia”. Al mismo tiempo, todas las páginas que enlaces desde tu página web (por ejemplo, este blog) recibirán, a su vez, una parte de la “importancia” de tu página.

Para ser más exactos:

2. Una página web reparte por igual su importancia entre todas las páginas a las que enlaza.

Es decir: Si te enlaza una página importante que enlaza 3 o 4 páginas a parte de la tuya es mucho mejor que si te enlaza una página igual de importante que enlace 30 o 40 (toca más Page Rank a repartir).

También habrás oído hablar de los Spiders (arañas). Estos no son más que veloces programas automáticos que van recorriendo internet como si fuesen un usuario humano, pulsando todos los enlaces posibles, extendiéndose así por la "red" (de ahí el nombre) y creando un mapa de la misma.

Así que tenemos:

3. Los Spiders proporcionan a Google un mapa de la red donde se puede ver qué página apunta a qué página.

¿Cómo calculamos el Page Rank? ¿Por qué página empezamos? Suponiendo que empezásemos por una, si no tenemos el Page Rank de las que enlazan a ésta, ¿cómo podemos calcular algo?

Y lo que es peor:

En internet hay 25.000.000.000 de páginas apuntándose unas a otras (número que está subiendo rápidamente). ¿Cómo crear un algoritmo que sea capaz de gestionar esa brutalidad de enlaces? En el peor caso, si todas las páginas se apuntan entre sí, el número total de enlaces es de 25.000.000.000, al cuadrado.

Vamos a explicar lo más sencillamente posible el algoritmo de  Larry y Sergei

Haz click en "más información" para continuar.

La Matriz de reparto de Page Rank H

No sabemos cuál es el Page Rank de ninguna página antes de empezar, pero si hay una cosa que sabemos: Cuanto de su desconocido Page Rank reparte una página entre las páginas que enlaza. Por lo dicho en (2), si una página enlaza 5 páginas transmitirá un 1/5 de su Page Rank a cada una. Debido a (3) el número de páginas que enlaza cada página lo sabemos. Es más, podemos construir una tabla H (matriz) de veinticinco mil millones de filas por veinticinco mil millones columnas (no, no cabe en un A4), que contenga todos los enlaces posibles.

Para dos páginas cualesquiera (una como enlazadora y la otra como enlazada) tenemos un recuadro de la tabla que nos indica que proporción del Page Rank transfiere la enlazadora a la enlazada. Para orientarnos un poco: La diagonal de esta tabla representaría lo que la página se transmite a si misma (si se enlazase). Cualquier recuadro por debajo de la diagonal y su simétrico por encima de la diagonal indican respectivamente lo que se transmiten dos páginas cuando una actúa como enlazadora y la otra como enlazada y viceversa. Si una página no enlaza a otra, se pone un 0 en el recuadro (lógicamente no le puede transmitir nada de Page Rank).

Matriz (Vector) Invariante I

Esta tabla (matriz), que hemos creado con la ayuda de la información proporcionada por los Spiders, representa en realidad la dificultad (o facilidad) para el "flujo" de Page Rank de una página a otra. Podemos ver el flujo como agua que pasa con menor o mayor dificultad de una página a otra de acuerdo al valor correspondiente al recuadro de la tabla H. Este agua/transferencia de Page Rank fluiría de una página a otra a través de sus enlaces sin cesar y eventualmente podría llegar a un equilibrio (si no llegase no habria Page Rank alguno).

El teorema de Ruelle-Perron–Frobenius nos garantiza lo siguiente:

4. Bajo determinadas condiciones, que veremos, se acabará alcanzando ese equilibrio. No es que Frobenius supiese lo que es una página web en 1900, sino que el problema es matemáticamente idéntico a un conocido problema de dinámica de sistemas.

5. El equilibrio queda representado por el vector invariante I. Esto es: Una tabla de una sola columna (una matriz, más concretamente vector) de 25.000.000.000 de valores, que cumple que al multiplicarla por la matriz de reparto H nos da otra vez ella misma (I). Lo que expresaríamos:

$$I=HI$$

Este vector invariante I de 25.000.000.000 de valores, uno para cada página web, es el Page Rank. Faltará refinarlo, escalarlo y discretizarlo a valores enteros de 1 a 10, y como se muestra en la google toolbar.

¿Y lo de las 25.000.000.000 páginas?

En álgebra,  I es un vector propio de valor propio 1 de la matriz H. Y para calcularlo hay que resolver un polinomio que en este caso tendría grado 25.000.000.000. Afortunadamente existe un método para calcular I iterativamente (en pasos sucesivos) y muy sencillo. Tan sencillo que consiste en que nos inventamos una tabla de 25.000.000.000 valores del Page Rank a voleo (un vector I₀ creado aleatoriamente), lo multiplicamos por H y el resultado será otra tabla de 25.000.000.000 valores I₁ pero más cercanos al valor correcto del vector invariante I. Se repite el proceso de multiplicar por H hasta que el vector I se estabiliza. Ya tenemos el vector invariante. Este algoritmo, que se llama el método de las potencias, se expresaría matemáticamente asi:

$$I^k^+^1=HI^k$$

Gran problema

¿Qué fácil, no? Obviamente falla algo y ese algo es el punto (4). Resulta que no se cumplen las condiciones de convergencia del teorema Ruelle-Perron–Frobenius. Es decir que aplicando el método arriba explicado no hay garantía de que lleguemos al vector invariante.

Utilizando la analogía del "flujo" de Page Rank se puede entender perfectamente que es lo que falla y como se puede solucionar.

Qué ocurre cuando el flujo de Page Rank llega a una página como la 2 que no tiene enlaces a ningún sitio? Pues simplemente que no sale de ahí. Esa página se vuelve un sumidero de Page Rank y el algoritmo dará resultados incorrectos.

¿Cómo lo resolvemos? Si hacemos la página 2 enlace todas las páginas de la web por igual (imagina millones de pequeñas flechas saliendo de 2 hacia todas las páginas), esto dará salida al flujo de Page Rank pero la influencia en los resultados es mínima, puesto que cada página recibe solo 1/25.000.000.000 del Page Rank de 2. Matemáticamente, esto equivale a sumarle a H una matriz A que tenga todo “ceros” menos en las columnas de las páginas sumidero que tendrán toda la columna llena de 1/25.000.000.000. De esta forma en vez de la matriz H emplearíamos la matriz S=H+A en el método de las potencias.

Red-Sumidero:

Un caso similar es el de las sub-redes de páginas dentro de la red, como la 5-7-6-8, que no tienen enlaces de vuelta. Estas redes se convierten en redes-sumidero. El problema es que estas páginas sí enlazan otras páginas y no podemos simplemente cargarnos esa información y enlazar todas las páginas de la red desde ellas.

Gran solución

Necesitamos garantizar la salida del flujo de Page Rank de cualquier página o sub-red, es decir, que toda página apunte a otra página. No nos vale con crear un enlace a cualquier página a voleo porque (aparte de estar falseando el Page Rank), si resulta en una red cerrada como 5-7-6-8 no hemos solucionado nada. Ahora, imaginemos un caso ideal en donde todas las páginas apuntasen a todas las páginas. Ahí el Page Rank siempre tendría algún enlace por donde escapar, incluso de las sub-redes, y el algoritmo funcionaría. Pero claro, se perdería toda la jerarquía que dan los enlaces, la matriz de reparto tendría todos sus elementos iguales a 1/25.000.000.000 y todas las páginas tendrían el mismo Page Rank.

Se suma la matriz de reparto real, calculada con la información de los Spiders, con la ideal en la que todas las páginas se apuntan entre sí y se divide por dos. La matriz resultante tendrá siempre enlaces saliendo de cada página y tenemos el flujo de Page Rank garantizado. Si al mezclar a partes iguales la matriz real y la ideal salen los resultados demasiado aleatorios (por influencia de la ideal), en vez de mitad y mitad se mezclan con 85% de la matriz real y un 15% de la ideal.

Se obtiene así  la famosa matriz de Google:

$$G=\alpha S+(1-\alpha)\frac{1}{n}*U$$

Donde recordemos que S=H+A es la matriz real con el problema de los sumideros individuales resuelto, 1/n×U, con n = 25.000.000.000 es la matriz ideal, U es la matriz de "unos" y α = 0.85 nos da la citada mezcla al 85%. Algún lector avispado puede decir: Pero… el meter ahí un 15% de aleatoriedad, ¿no falsea de alguna manera el Page Rank?

Para terminar si empleamos G en vez de H en el método de las potencias y se obtiene

$$GI^k=\alpha HI^k +\alpha AI^k+\frac{1-\alpha}{n}UI^k$$

Empleando la fórmula a la derecha del igual obtendremos cada nuevo vector I_k+1 en cada iteración

Anotaciones finales

Este artículo ha sido elaborado a partir de esta interesante página y ahí van algunas aclaraciones:

El valor óptimo del parámetro α se determina experimentalmente y regula también la velocidad de convergencia del método de las potencias, a mayor porcentaje de matriz real, menor velocidad de convergencia. Google dice que con basta con k=50-100 iteraciones para calcular el Page Rank, cosa que tarda varios días y suponemos que que trabajando con varios ordenadores en paralelo. Esto se conoce como Google Dance. 

Matemáticamente, la condición de convergencia del algoritmo empleado por Google es que todos los elementos de la matriz de reparto de Page Rank sean estrictamente mayores que 0. Esto no es una condición de convergencia del método de las potencias sino una condición para la existencia del vector invariante según el teorema de Ruelle-Perron–Frobenius.