El algoritmo del PageRank de Google, es decir, la fórmula que utiliza para calcular el PageRank de una página es uno de los mayores y más deseados secretos de Internet.
El algoritmo PageRank
El algoritmo original del PageRank ha sido descrito en varias ocasiones por Lawrence Page y Sergey Brin. Es el siguiente:
PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
Las variables son:
- PR(A) Es el PageRank de la página A,
- PR(Ti) Es el PageRank de las páginas Ti que enlazan a A,
- C(Ti) Es el número de links salientes de la página Ti
- d es un factor variable que puede estar entre 0 y 1.
Así pues, lo primero de todo, vemos que el PageRank no se aplica a un sitio Web en su totalidad, sino a sus páginas individualmente. Además, el PageRank de la página A se define de forma recursiva por el PageRanks de las páginas que enlazan a esa página A.
El PageRank de las páginas Ti que enlazan a la página A no afecta al PageRank de la página A uniformemente. Dentro del algoritmo del PageRank, el PageRank de una página T se calcula por el número de links salientes C (T) en la página T. Esto significa que cuantos más enlaces salientes tenga la página T, menos beneficiará el anlace de la página A al enlazar a la página T.
El PageRank transmitido de las páginas Ti se suma. La consecuencia de esto es que otros enlaces adicionales a la página A aumentarán siempre el PageRank de la página A.
Finalmente, la suma del PageRank transmitido de las páginas Ti se multiplica por un factor aleatorio d que puede estar entre 0 y 1. De este modo, la transmisión del PageRank que beneficia a una página que es enlazada por otra se reduce.
El Modelo Navegación Aleatoria
Lawrence Page y Sergey Brin justifican de una forma simple e intuitiva el funcionamiento del algoritmo PageRank. Consideran el PageRank como un modelo del comportamiento del usuario, donde una persona que navega cliquea en enlaces al azar sin reparar en el contenido.
El usuario que visita una página puede cambiar o influir en el PageRank de la página. La probabilidad de que el ususario presione un enlace solo depende del número de enlaces de la página. Esta es la razón por la cual el PageRank transmitido a una página que se enlaza disminuye, ya que se divide entre los links de la página. Así pues, la probabilidad para el usuario de presionar sobre ese link en concreto depende del número de links de la página. Ahora, esta probabilidad se reduce por el factor aleatorio d. La explicación de este “Modelo de Navegación Aleatoria”, por lo tanto, es que el usuario no puede presionar sobre un número infinito de links, pero acaba cansándose y se va a otra página.
La probabilidad de que el usuario no deje de presionar el enlace viene dada por el factor d, que está, dependiendo del grado de probabilidad por lo tanto, entre 0 y 1. El d más alto es la probabilidad más alta de que el usuario presione en el enlace. Puesto que el usuario sale de la página cuando deja de presionar sobre los enlaces, la probabilidad se define como la constante (1-d) en el algoritmo. Sin tener en cuenta los enlaces entrantes, la probabilidad de que el usuario presione el link es siempre (1-d), así que una página siempre tiene el PageRank mínimo.
Otra versión del algoritmo PageRank
Lawrence Page y Sergey Brin have han publicado varias versiones del algoritmo del PageRank. Otra formulación determina el PageRank de A según la fórmula:
PR(A) = (1-d) / N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
- N es el número total de páginas del sitio
La segunda versión del algoritmo no se diferencia mucho de la primera. Con respecto al Modelo de Navegación Aleatoria, El PageRank de esta versión es la probabilidad real de que el usuario presione sobre el link entre todos los que existen. El PageRank es, entonces, la probabilidad uniforme entre todas las páginas, así que la suma de los PageRanks de todas las páginas será el mismo.
Por el contrario, en la primera versión del algoritmo la probabilidad de presionar el enlace viene dado por el número total de páginas. En esta versión, el PageRank es un valor previsto para el usuario cuando entra tan a menudo como páginas tiene el sitio. Es decir, si un sitio tiene 100 páginas y una página tiene un PageRank 2, el usuario tendrá el doble de probabilidades de llegar a esa página si repite la llegada a la página 100 veces.
Como se menciona arriba, no hay muchas diferencias entre la dos versiones. El PageRank calculado con la segunda versión del algoritmo tiene que ser multiplicado por el número total de páginas del sitio para que coincida con el PageRank calculado con la primera versión del algoritmo. Los autores reivindican el uso del primer algoritmo en su obra más famosa “The Anatomy of a Large-Scale Hypertextual Web Search Engine” para calcular el PageRank de un sitio como la suma de los PageRanks de todas las páginas.
A partir de ahora, utilizaremos la primera versión del algritmo para hacer cálculos ya que de esta forma evitamos el parámetro del número total de páginas.
Características del PageRank
Las características del PageRank pueden explicarse con un pequeño ejemplo:
Tenemos un sitio con tres páginas, A, B y C, donde A enlaza B y C, B enlaza C, y C enlaza A. De acuerdo con el algoritmo, el factor aleatorio d es de 0.85, pero para simplificar los cálculos lo redondeamos a 0.5. Este factor d sabemos que afecta al PageRank, pero no afecta a los principios del PageRank. Así que hagamos unos cálculos:
PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))
Estas ecuaciones son sencillas. Nos queda el siguiente PageRank para cada página:
PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615
Como es obvio, el PageRank de la suma de las páginas es 3, igual que el número de páginas. Este resultado no es específico de nuestro sencillo ejemplo.
En nuestro caso es facil calcularlo directamente ya que solo tenemos 3 páginas. Pero actualmente los sitios están formados por miles de páginas, luego es necesario algún otro sistema de cálculo.
El método iterativo del PageRank
Debido al tamaño actual de la Web, el buscador de Google usa un valor iterativo aproximado de PageRank. Esto significa que a cada página se le asigna un valor inicial de PageRank, y después el PageRank de todas las páginas se calcula con cálculos cíclicos basados en la fórmula del algoritmo de PageRank. Este cálculo iterativo puede representarse para nuestro ejemplo de tres páginas con un valor inicial de pageRank para cada página de 1:
| Iteration | PR(A) | PR(B) | PR(C) |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0.75 | 1.125 |
| 2 | 1.0625 | 0.765625 | 1.1484375 |
| 3 | 1.07421875 | 0.76855469 | 1.15283203 |
| 4 | 1.07641602 | 0.76910400 | 1.15365601 |
| 5 | 1.07682800 | 0.76920700 | 1.15381050 |
| 6 | 1.07690525 | 0.76922631 | 1.15383947 |
| 7 | 1.07691973 | 0.76922993 | 1.15384490 |
| 8 | 1.07692245 | 0.76923061 | 1.15384592 |
| 9 | 1.07692296 | 0.76923074 | 1.15384611 |
| 10 | 1.07692305 | 0.76923076 | 1.15384615 |
| 11 | 1.07692307 | 0.76923077 | 1.15384615 |
| 12 | 1.07692308 | 0.76923077 | 1.15384615 |
Puede verse una buena aproximación del valor del PageRank real tras solo unas pocas repeticiones. El número mínimo de Iteraciones necesario para que el PageRank sea válido es de 100 en todo el sitio.
También, por medio del cálculo iterativo, la suma de PageRanks de todas las páginas converge con el número total de Web pages. El PageRank medio de una página es 1. El PageRank mínimo de una página se asigna por (1-d). Por lo tanto, hay un PageRank máximo para una página que se asigna por dN+ (1-d), donde el número N es el total de páginas. Este máximo puede ocurrir teóricamente, si todas las páginas enlazan solamente a una página, y esta página también se enlaza a sí misma.
Traducción del artículo: The PageRank Algorithm
