El algoritmo PageRank de Google, explicado – Search Engine Watch

Hoy temprano, Dixon Jones de Majestic compartió Twitter una explicación completa y digerible de cómo funciona realmente PageRank.

Yo mismo le di un reloj y pensé que era un buen momento para volver a visitar esta salvaje pieza matemática que ha hecho mella en el mundo durante los últimos 20 años.

Como nota al margen, sabemos a partir de 2017 que, si bien PageRank se eliminó de la barra Google en 2016, todavía forma una parte importante del algoritmo de clasificación general, y por eso vale la pena entenderlo.

Jones comienza con la fórmula simple, o al menos sencilla.

algoritmo de pagerank

Para aquellos que no adoran las matemáticas, o que pueden haber olvidado algunos términos técnicos desde la última clase de cálculo, esta fórmula se leería en voz alta así:

“El PageRank de una página en esta iteración es igual a 1 menos un factor de amortiguación, más, por cada enlace a la página (excepto los enlaces a sí misma), agregue el rango de página de esa página dividido por el número de enlaces salientes en la página y reducido por el factor de amortiguación “.

Volver al documento original de Google

En este punto, Jones avanza en el video hacia una versión más simple y útil del cálculo. Saca Excel, un visual sencillo de 5 nodos, y traza el algoritmo de clasificación en 15 iteraciones. Buena cosa.

Personalmente, quería un poco más de matemáticas, así que volví y leí la versión completa de “La anatomía de un motor de búsqueda web hipertextual a gran escala”(Un primer paso natural). Este fue el artículo escrito por Larry Page y Sergey Brin en 1997. También conocido como el artículo en el que presentaron Google, publicado en el Departamento de Ciencias de la Computación de Stanford. (Sí, es largo y trabajaré un poco tarde esta noche. ¡Todo muy divertido!)

¿Cómo es esto para una línea de apertura?En este artículo presentamos Google, un prototipo de motor de búsqueda a gran escala que hace un uso intensivo de la estructura presente en el hipertexto.

Informal, según su estilo general y continuo.

Como dato extra divertido, ¡nuestro propio Search Engine Watch fue citado en ese artículo de presentación de Google! Nada menos que por Page y Brin, afirmando que ya existían 100 millones de documentos web en noviembre de 1997.

De todos modos, volvamos al trabajo.

Así es como se definió originalmente el cálculo de PageRank:

“La literatura de citas académicas se ha aplicado a la web, en gran parte contando las citas o los vínculos de retroceso a una página determinada. Esto da una aproximación de la importancia o la calidad de una página. PageRank amplía esta idea al no contar los enlaces de todas las páginas por igual y al normalizar por el número de enlaces en una página. PageRank se define de la siguiente manera:

Suponemos que la página A tiene páginas T1… Tn que apuntan a ella (es decir, son citas). El parámetro d es un factor de amortiguación que se puede establecer entre 0 y 1. Por lo general, establecemos d en 0,85. Hay más detalles sobre d en la siguiente sección. También C (A) se define como el número de enlaces que salen de la página A. El PageRank de una página A se da de la siguiente manera:

PR (A) = (1-d) + d (PR (T1) / C (T1) +… + PR (Tn) / C (Tn))

Tenga en cuenta que los PageRanks forman una distribución de probabilidad en las páginas web, por lo que la suma de los PageRanks de todas las páginas web será uno.

PageRank o PR (A) se puede calcular usando un algoritmo iterativo simple, y corresponde al vector propio principal de la matriz de enlaces normalizada de la web. Además, se puede calcular un PageRank para 26 millones de páginas web en unas pocas horas en una estación de trabajo de tamaño mediano. Hay muchos otros detalles que están más allá del alcance de este documento “.

¿Qué significa eso?

¡Ten paciencia con nosotros! Aquí está nuestra fórmula nuevamente:

PR (A) = (1-d) + d (PR (T1) / C (T1) +… + PR (Tn) / C (Tn))

Tenga en cuenta que esto es lo mismo que la imagen de arriba, excepto que la foto “simplifica” la segunda parte de la ecuación sustituyendo un sigma en mayúsculas (∑), que es el símbolo de una suma matemática, es decir, haga esta fórmula para todas las páginas 1 hasta ny luego súmelos.

Entonces, para calcular el PageRank de la página A dada, primero tomamos 1 menos el factor de amortiguación (d). D normalmente se establece en .85, como se ve en su documento original.

Luego tomamos los PageRanks de todas las páginas que apuntan hacia y desde la página A, los sumamos y multiplicamos por el factor de amortiguación de 0.85.

No está tan mal, ¿verdad? Es más fácil decirlo que hacerlo.

PageRank es un algoritmo iterativo

Quizás tus ojos se pusieron vidriosos sobre esta parte, pero Brin y Sergey en realidad usaron la palabra “autovector” en su definición. Tuve que buscarlo.

Aparentemente, los vectores propios juegan un papel destacado en las ecuaciones diferenciales. El prefijo “eigen” proviene del alemán para “propio” o “característico”. También existen valores propios y ecuaciones propias.

Como señaló Rogers en su artículo clásico sobre PageRank, lo más importante para nosotros acerca de la pieza de vector propio es que es un tipo de matemática que le permite trabajar con múltiples partes móviles. “Podemos seguir adelante y calcular el PageRank de una página sin conocer el valor final del PR de las otras páginas. Eso parece extraño pero, básicamente, cada vez que ejecutamos el cálculo obtenemos una estimación más cercana del valor final. Así que todo lo que tenemos que hacer es recordar cada valor que calculamos y repetir los cálculos muchas veces hasta que los números dejen de cambiar mucho “.

O en otras palabras, el La importancia del vector propio es que PageRank es un algoritmo iterativo. Cuantas más veces repita el cálculo, más se acercará a los números más precisos.

PageRank visualizado en Excel

En su video, Jones va directo a la parte divertida, razón por la cual es tan efectivo en solo 18 minutos. Demuestra cómo se calcula el PageRank con el ejemplo de 5 sitios web que se enlazan entre sí.

Luego lo devuelve a los cálculos en Excel:

Y demuestra cómo iteraría tomando la fila de números en la parte inferior y repitiendo el cálculo.

Al hacer esto, el los números eventualmente comienzan a nivelarse (esto fue después de solo 15 iteraciones):

O como algunos podrían titular esta foto, “Autovectores en la naturaleza”.

Otras observaciones interesantes que plantea Jones:

  1. Los recuentos de enlaces (solo números totales) son una mala métrica. Necesitamos preocuparnos más por la clasificación de cada página.
  2. Es el ranking en el el nivel de página que cuenta, no la autoridad del dominio. PageRank solo miraba páginas individuales.
  3. La mayoría de las páginas apenas tienen rango. En su ejemplo, los 3 primeros de 10 representaron el 75-80% del ranking total.

Así que finalmente, aquí está el tweet original que me llevó a este largo y fascinante agujero de conejo. ¡Espero que disfruten de lo mismo!

Aquí tienes. Cómo funciona REALMENTE PageRank https://t.co/OO7J0KChsr cc @RyanJones y @JosephKlok y cualquier otra persona que desee retuitear.

– Dixon (@Dixon_Jones) 25 de octubre de 2018