formula-algoritmo-page-rank-google

Algoritmo PageRank de Google, como funciona

Recientemente Dixon Jones de Majestic compartió en Twitter una explicación completa y digerible de cómo funciona realmente el PageRank, el algoritmo de google.

Le he dado un vistazo a su explicación, y pensé que era un buen momento para volver a visitar esta trozo salvaje de matemáticas que ha hecho mella en el mundo en los últimos 20 años.

Como nota lateral, sabemos desde 2017 que aunque PageRank fue eliminado de la barra de herramientas en 2016, sigue siendo una parte importante del algoritmo de clasificación general y, por lo tanto, vale la pena entenderlo.

Jones comienza con la fórmula simple – o al menos, directa -.

formula-algoritmo-page-rank-google

Para aquellos que no adoran las matemáticas, o que han olvidado algunos términos técnicos desde la última clase de cálculo, esta fórmula se lee en voz alta de esta manera:

“El PageRank de una página en esta iteración es igual a 1 menos un factor de amortiguamiento, además, para cada enlace en la página (excepto para los enlaces a sí mismo), añade 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 amortiguamiento”.

Volver al documento original de Google

En este punto, Jones avanza en el video a una versión más simple y útil del cálculo. Saca excel, un visual fácil de 5 nodos, y mapea el algoritmo de clasificación en 15 iteraciones. Muy buen material.

Personalmente, quería un poco más de matemáticas, así que volví y leí la versión completa de “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (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 Informática de Stanford. (Sí, es largo y voy a trabajar un poco tarde esta noche. ¡Todo por diversión!)

¿Qué te parece esta primera frase? “En este artículo, presentamos Google, un prototipo de un motor de búsqueda a gran escala que hace un uso intensivo de la estructura presente en el hipertexto.”

Casuales, por su estilo general y continuo.

Como un hecho extra divertido, nuestro propio Search Engine Watch fue citado en el primer artículo de Google! Por nada menos que Page y Brin mismos, afirmando que ya existían 100 millones de documentos web en noviembre de 1997.

De todos modos, de vuelta al trabajo.

Así es como se definió originalmente el cálculo del PageRank:
“La literatura de citas académicas se ha aplicado a la web, en gran medida contando citas o vínculos de retroceso a una página determinada. Esto da alguna aproximación de la importancia o 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. El PageRank se define de la siguiente manera:

Asumimos 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 ajustar entre 0 y 1. Normalmente se ajusta d a 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 como sigue:

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 sobre las páginas web, por lo que la suma de los PageRanks de todas las páginas web será una.

PageRank o PR(A) puede calcularse utilizando un algoritmo iterativo simple, y corresponde al vector propio principal de la matriz de enlaces normalizados de la web. Además, un PageRank para 26 millones de páginas web puede calcularse en pocas horas en una estación de trabajo de tamaño medio. Hay muchos otros detalles que están fuera del alcance de este documento”.

¿Qué significa eso?

Tengan paciencia con nosotros! Aquí está nuestra fórmula otra vez:

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

Nótese que esto es lo mismo que la imagen de arriba, excepto que la foto “simplifica” la segunda parte de la ecuación sustituyendo una sigma en mayúsculas (∑), que es el símbolo de una suma matemática, es decir, hacer esta fórmula para todas las páginas de la 1 a la n y luego sumarlas.

Así que para calcular el PageRank de una página A dada, primero tomamos 1 menos el factor de amortiguación (d). D se fija normalmente en 0,85, como se ve en el papel 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

Tal vez sus ojos estaban vidriosos sobre esta parte, pero Brin y Sergey en realidad usaron la palabra “eigenvector” en su definición. Tuve que buscarlo.

Aparentemente, los vectores propios juegan un papel prominente en las ecuaciones diferenciales. El prefijo “eigen” viene del alemán para “proper” o “characteristic”. También existen valores propios y ecuaciones propias.

Como Rogers señaló en su clásico artículo sobre PageRank, la mayor ventaja para nosotros acerca de la pieza eigenvector es que es un tipo de matemática que te permite trabajar con múltiples partes móviles. “Podemos 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 hacemos el cálculo estamos obteniendo 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”.

En otras palabras, la importancia del propio eigenvector es que PageRank es un algoritmo iterativo. Cuantas más veces repita el cálculo, más cerca estará de los números más exactos.

PageRank visualizado en Excel

En su video, Jones va directo a la parte divertida, por eso es tan efectivo en tan sólo 18 minutos. Él 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ías tomando la fila de números en la parte inferior y repitiendo el cálculo.

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

 

 

 

 

 

O como algunos dirían en esta foto: “Vectores propios en la naturaleza”.

Otras observaciones interesantes que hace Jones:

Los recuentos de enlaces (sólo números totales) son una mala métrica. Necesitamos preocuparnos más por el rango de cada página.
Lo que cuenta es el ranking a nivel de página, no la autoridad del dominio. PageRank sólo ha mirado páginas individuales.
La mayoría de las páginas no tienen apenas ningún rango. En su ejemplo, los 3 primeros de 10 representaron el 75-80% de la clasificación total.
Así que finalmente, aquí está el tweet original que me llevó a esta larga y fascinante madriguera de conejos. Espero que todos disfruten de lo mismo!

 

Deja un comentario

A %d blogueros les gusta esto: