14.1 Google: Page Rank
El Algoritmo que puso a Google a dominar el mundo
Introducción a PageRank Imperial College
Introducción
Imagine una biblioteca que contiene 25 mil millones de documentos pero sin organización centralizada y sin bibliotecarios. Además, cualquier persona puede agregar un documento en cualquier momento sin decírselo a nadie. Usted puede sentior que uno de los documentos contenidos en la colección tiene un dato que es de vital importancia para usted y, siendo impaciente como la mayoría de nosotros, le gustaría encontrarlo en un asunto de segundos.
Planteado de esta forma, el problema parece imposible. Sin embargo, esta descripción no es demasiado diferente de la World Wide Web, una colección enorme y muy desorganizada de documentos en muchos formatos diferentes. Por supuesto, todos estamos familiarizados con los mnotores de búsqueda, por lo que sabemos que hay una solución.Describiremos el algoritmo PageRank de Google y cómo devuelve páginas de la colección de 25 mil millones de documentos que coinciden con los criterios de búsqueda ( de hecho el verbo googlear pertenece ahora al diccionario de la Real Academia de la Lengua).
Motores de Búsqueda
La mayoría de los motores de búsqueda, incluido Google, ejecutan continuamente un ejército de programas que recuperan páginas de la web, indexan las palabras en cada documento y almacenan esta información en un formato eficiente. Cada vez que un usuario solicita una búsqueda web utilizando una frase de búsqueda, como "motor de búsqueda", el motor de búsqueda determina todas las páginas de la web que contienen las palabras de la frase de búsqueda. Aquí está el problema, aproximadamente el 95% del texto de las páginas web se compone de tan solo 10.000 palabras. Esto significa que, para la mayoría de las búsquedas, habrá una gran cantidad de páginas que contienen las mismas palabras en la frase de búsqueda. Lo que se necesita es un medio para clasificar la importancia de las páginas que se ajustan a los criterios de búsqueda para que las páginas se puedan ordenar con las páginas más importantes en la parte superior de la lista.
Una forma de determinar la importancia de las páginas es utilizar una clasificación sugerida por seres humanos, por ejemplo, es posible que haya visto páginas que constan principalmente de una gran cantidad de enlaces a otros recursos en un área de interés particular. Asumiendo que la persona que mantiene esta página es confiable, es probable que las páginas a las que se hace referencia sean útiles. Por supuesto, la lista puede quedar desactualizada rápidamente y la persona que mantiene la lista puede perder algunas páginas importantes, ya sea de forma no intencionada o como resultado de un sesgo no declarado. El algoritmo PageRank de Google evalúa la importancia de las páginas web sin la intervención del ser humano para la evaluación del contenido. De hecho, Google siente que el valor de su servicio está en gran parte en su capacidad para proporcionar resultados imparciales a las consultas de búsqueda; Google afirma "el corazón de nuestro software es PageRank ".
El truco consiste en pedirle a la misma web que clasifique importancia de las páginas.
¿Cómo saber qué es importante?
Si alguna vez ha creado una página web, probablemente haya incluido enlaces a otras páginas que
contienen información valiosa y confiable. Al hacerlo, está dándole importancia de las páginas a las que enlaza. El algoritmo PageRank de Google genera un concurso entre todas las páginas de la web para decidir qué páginas son las más importantes. la idea fundamental presentada por los creadores de PageRank, Sergey Brin y Lawrence Page, es esta:
la importancia de una página se juzga por el número de páginas que enlazan a ella y por su propia importancia.
Asignaremos a cada página web P una medida de su importancia I(P), denominada Rankeo de página (PageRank). Así es como se determina el PageRank. Suponga que la página P(j) tiene l(j) enlaces. Si uno de esos enlaces es a la página P(i), entonces P(j) pasará 1 /l(j) de su importancia a P(i). El Ranking de importancia de P(i) es entonces la suma de todas las contribuciones realizadas por las páginas enlazando a él. Es decir, si denotamos el conjunto de páginas que enlazan con P(i) por B(i), entonces: Esto puede recordarle el problema del huevo y la gallina: para determinar la importancia de una página, primero debemos conocer la importancia de todas las páginas que enlazan con ella. Sin embargo, se puede reformular el problema en uno que sea matemáticamente más familiar. Primero creemos una matriz, llamada matriz de hipervínculos, la fila i, columna j de la matriz es:
Note que H tiene algunas propiedades especiales. Primero, sus entradas son todas no negativas. También, la suma de las entradas de las columnas es uno, a menos que la página correspondiente a esa columna no tenga enlaces. Matrices en las que todas las entradas son no negativas y la suma de las entradas en cada columna hay una que se llama estocástica; ellas jugarán un papel importante en nuestra historia. También formaremos un vector I=I(Pi)
cuyos componentes son PageRanks, es decir, las clasificaciones de importancia de todas las páginas. La condición anterior que define el PageRank puede expresarse como:
En otras palabras, el vector I es un vector propio de la matriz H con valor propio 1. Se llama también o un vector estacionario de H.
Un Ejemplo
Veamos un ejemplo. A continuación se muestra una representación de una pequeña colección de ocho páginas web con enlaces representados por flechas:
La matriz correspondiente es:
y el vector estacionario correspondiente es:
Esto muestra que la página 8 gana el concurso de popularidad.
La misma figura con las páginas web sombreadas de tal manera que las páginas con PageRanks más altos son más claras es la siguiente:
