El algoritmo de Google

Method for node ranking in a linked database

(M?do para la jerarquizaci?e nodos en una base de datos enlazada)

La patente m?famosa de Google es una de las principales ventajas competitivas que permiti?esta compa?aplastar a sus competidores en el campo de las busquedas 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?na web determinada. Esta «importancia» se emplea despu?para mostrar los resultados de mayor calidad cuando realizamos una b?eda en Google. La calidad de los resultados de Google empleando este m?do (combinado, por supuesto, con otros algoritmos) es lo que nos hizo a todos abandonar nuestros antiguos buscadores (Altavista, Metacrawler) y pasarnos al buscador de Larry y Sergei. Aqu?n thesmokesellers estamos un poco quemados con el hecho haber bajado de Page Rank y hemos estado intentando hincarle el diente estos d?. En este post vamos a explicar el algoritmo hasta el final intentando emplear la cantidad m?ma de matem?cas posibles.

(*) goran opina que otra de las principales ventajas competitivas de Google fue llenar una piscina olimpica de sangre de ni?no bautizados y ofrecer su buscador a Satan.

Si alguna vez te has interesado por el tema, habras leido que:

1. La «importancia» de una p?na web s?depende de las paginas web que la enlazan.

Si tienes una p?na web y esta es enlazada desde p?nas importantes (de alto Page Rank, pongamos www.microsiervos.com) t?cibiras una parte de esa importancia. Todas las p?nas que enlaces desde tu p?na web (ese blog de tu colega con solo dos posts, por ejemplo) recibiran, a su vez, una parte de la importancia de TU p?na. Para ser m?exactos:

2. Una p?na web reparte por igual su importancia entre todas las p?nas a las que enlaza.

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

Tambien habras oido hablar de los Spiders (ara?. Esto no son m?que veloces programas autom?cos que van recorriendo internet como si fuesen un usuario humano, pulsando todos los enlaces posibles, extendiendose as?or la «red» (de ahi el nombre) y creando un mapa de la misma. Asi que tenemos:

3. Los Spiders proporcionan a Google un mapa de la red donde se puede ver qu??na apunta a que p?na

Esto no significa que sepamos ya el Page Rank. De hecho, todo esto es muy bonito pero… como leches calculamos el Page Rank?. Por qu??na empezamos?. Suponiendo que empezasemos por una, si no tenemos el Page Rank de las que enlazan a esta, como podemos calcular algo?. Y lo que es peor: En internet hay venticincomil millones de p?nas apuntandose unas a otras (n?o subiendo r?damente), c?crear un algoritmo que sea capaz de lidiar con semejante brutalidad de enlaces. En el peor caso todas las p?nas se apuntan entre si y el numero total de enlaces es de venticincomil millones, al cuadrado!!.

Aqui es donde realmente llega la artilleria matem?ca. Prometemos que si sabes lo que es una matriz, como se suman y como se multiplican (y tienes un poco de fe) ya puedes entender el algoritmo de Larry y Sergei hasta el final.

La Matriz de reparto de Page Rank H

Vale, no sabemos cual es el page Rank de ninguna p?na antes de empezar, pero si hay una cosa que sabemos: Cuanto de su desconocido Page Rank reparte una p?na entre las p?nas que enlaza. Por lo dicho en (2), si una p?na enlaza 5 p?nas transmitira un 1/5 de su Page Rank a cada una. Debido a (3) el n?o de p?nas que enlaza cada p?na lo sabemos. Es m? podemos construir una tabla H 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?nas cualesquiera (una como enlazadora y la otra como enlazada) tenemos un recuadro de la tabla que nos indica que proporci?el Page Rank transfiere la enlazadora a la enlazada. Para orientarnos un poco: La diagonal de esta tabla representar?lo que la p?na se transmite a si misma (si se enlazase). Cualquier recuadro por debajo de la diagonal y su simetrico por encima de la diagonal indican respectivamente lo que se transmiten dos p?nas cuando una actua como enlazadora y la otra como enlazada y viceversa. Si una p?na no enlaza a otra, se pone un 0 en el recuadro (l?amente no le puede transmitir nada de Page Rank).

Matriz (Vector) Invariante I

Lo que viene a continuaci?o es idea de Larry Page o Sergei Brin, hace un siglo que se conoce, pero si que requiere la poca de fe que te pedimos reservar. Esta tabla (lease Matriz), que hemos creado con la ayuda de la informaci?roporcionada por los Spiders, representa en realidad la dificultad (o facilidad) para el «flujo» de Page Rank de una p?na a otra. Podemos ver el flujo como agua que pasa con menor o mayor dificultad de una p?na a otra de acuerdo al valor correspondiente al recuadro de la tabla H. Este agua/transferencia de Page Rank fluir?de una p?na a otra a traves de sus enlaces sin cesar y eventualmente podr?llegar a un equilibrio (si no llegase no habria Page Rank alguno). Pues bien las matem?cas, concretamente el teorema de Ruelle-Perron–Frobenius (ingles) nos garantiza lo siguiente:

4. Bajo determinadas condiciones, que veremos, se acabar?lcanzando ese equilibrio. No es que Frobenius (ingles) supiese lo que es una p?na web en 1900, si no que el problema es matem?camente id?ico a un conocido problema de din?ca de sistemas (ingles). Luego, hay gente que dice que Larry y Sergei son licenciados en filosof?

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

Este vector invariante I de venticincomil millones de valores, que casualidad, uno para cada p?na web, es el Page Rank. Faltar?efinarlo, escalandolo de 1 a 10, y discretizarlo para que no de valores intermedios. Intuyo que el valor discretizado (1 a 10 sin decimales), que se muestra en la google toolbar, es solo de cara al publico e internamente emplearan los decimales que salgan tambi?

S?muy guay pero y lo de las 25.000.000.000 p?nas?

Cierto, cierto. La gente que haya sufrido algebra de primero habra reconocido a I como un vector propio de valor propio 1 de la matriz H. Y seguramente recordar?on horror que para calcularlo hay que resolver un polinomio que en este caso tendr?grado 25.000.000.000. Vamos no lo calculamos asi ni de blas. Afortunadamente, sobre todo para las personas a las que lo anterior les ha sonado a chino, existe un m?do para calcular I iterativamente (en pasos sucesivos) y muy 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 I0 creado aleatoriamente), lo multiplicamos por H y el resultado ser?tra tabla de 25.000.000.000 valores I1 pero m?cercanos al valor correcto del vector invariante I. Rep?se esto un monton de veces hasta que el resultado de multiplicar por H ya no produzca nigun cambio y ya est?Ya tenemos el vector invariante. Este algoritmo, que se llama el m?do de las potencias (ingles), se expresar?matem?camente asi:

Donde k no es m?de que el ?ice que indica cuantas veces hemos multiplicado por la matriz H. El primer vector, que creariamos a boleo ser?k = 0, el segundo, procedente de mutiplicar por H ser?k =1, etc. Para expresar de forma general que cada t?ino se obtiene mediante una transformacion del anterior se emplean los ?ices k+1 y k. Hay que tener en cuenta que los m?dos iterativos tienen la ventaja de que no necesitamos acumular demasiados valores, lo cual reduce la cantidad de memoria que necesitamos para computar el Page Rank y acelera todo el proceso de c?ulo. Siguen siendo una burrada de n?os pero al menos es factible.

Gran problema

Que facil, 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?do arriba explicado no hay garant?de que lleguemos al vector invariante. No entrar?n detalles, no hace falta. Utilizando la analog?del «flujo» de Page Rank se puede entender perfectamente que es lo que falla y como se puede solucionar.

P?na Sumidero:

Qu?curre cuando el flujo de Page Rank llega a una p?na como la 2 que no tiene enlaces a nig?itio?. Pues simplemente que no sale de ahi. Esa p?na se vuelve un sumidero de Page Rank y el algoritmo dar?esultados incorrectos. Como lo resolvemos?. Si hacemos la p?na 2 enlace todas las p?nas de la web por igual (imagina millones de peque?flechas saliendo de 2 hacia todas l?p?nas), esto dar?alida al flujo de Page Rank pero la influencia en los resultados es minima, puesto que cada p?na recibe solo 1/25.000.000.000 del Page Rank de 2. Matem?camente, esto equivale a sumarle a H una matriz A que tenga todo 0s menos en las columnas de las p?nas sumidero que tendr?toda la columna llena de 1/25.000.000.000. De esta forma en vez de la matriz H emplear?os la matriz S=H+A en el m?do de las potencias.

Red-Sumidero:

Un caso similar es el de las sub-redes de p?nas 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?nas s?nlazan otras p?nas y no podemos simplemente cargarnos esa informaci? enlazar todas las p?nas de la red desde ellas. Para dar salida al flujo de Page Rank, vamos a recurrir a una soluci?l m?puro estilo «ingeniero».

Gran soluci?strong>