ALGORITMO DE PAGE RANK

Algoritmos de Google: El Page Rank

Method for node ranking in a linked database

(Método para la jerarquización de nodos en una base de datos enlazada)
La patente más famosa de Google es una de las principales ventajas competitivas que permitió a esta compañia aplastar a sus competidores en el campo de las busquedas en internet y hacerse el gigante que son hoy*. El Page Rank, como todos laconocemos, 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 los resultados de mayor calidad cuando realizamos una búsqueda en Google. La calidad de los resultados de Google empleando este método (combinado, por supuesto, con otros algoritmos) es lo que nos hizo a todos abandonar nuestros antiguosbuscadores (Altavista, Metacrawler) y pasarnos al buscador de Larry y Sergei. Aquí en The Smoke Sellers estamos un poco quemados con el hecho haber bajado de Page Rank y hemos estado intentando hincarle el diente estos días. En este post vamos a explicar el algoritmo hasta el final intentando emplear la cantidad mínima de matemáticas posibles.
(*) goran opina que otra de las principales ventajascompetitivas de Google fue llenar una piscina olimpica de sangre de niños 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ágina web sólo depende de las paginas web que la enlazan.
Si tienes una página web y esta es enlazada desde páginas importantes (de alto Page Rank, pongamos www.microsiervos.com) tú recibirasuna parte de esa importancia. Todas las páginas que enlaces desde tu página web (ese blog de tu colega con solo dos posts, por ejemplo) recibiran, 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 dela 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).
Tambien habras oido hablar de los Spiders (arañas). Esto no son más que veloces programas automáticos que van recorriendo internet como si fuesen un usuario humano, pulsando todos los enlaces posibles, extendiendose así por la "red" (de ahi el nombre) y creando un mapa de lamisma. Asi que tenemos:
3. Los Spiders proporcionan a Google un mapa de la red donde se puede ver qué página apunta a que página
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é página empezamos?. Suponiendo que empezasemos por una, si no tenemos el Page Rank de las que enlazan a esta, como podemos calcularalgo?. Y lo que es peor: En internet hay venticincomil millones de páginas apuntandose unas a otras (número subiendo rápidamente), cómo crear un algoritmo que sea capaz de lidiar con semejante brutalidad de enlaces. En el peor caso todas las páginas se apuntan entre si y el numero total de enlaces es de venticincomil millones, al cuadrado!!.
Aqui es donde realmente llega la artilleria matemática.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á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 transmitira 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 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...