4 Algoritmo PageRank

A finales de la década de 1990, cuando Google entró en línea, un factor clave que lo distinguía de otros motores de búsqueda era su capacidad para ofrecer constantemente los resultados más relevantes en la parte superior de las listas de búsqueda. A diferencia de otros motores de búsqueda, donde los usuarios a menudo tenían que cribar páginas de enlaces irrelevantes que simplemente coincidían con la consulta de búsqueda, Google presentaba una experiencia más optimizada.

Esta magia reside en parte en el algoritmo PageRank de Google. Este algoritmo asigna un valor cuantitativo a cada página web, valorando esencialmente su importancia. Al aprovechar PageRank, Google puede clasificar las páginas web y priorizar las más importantes (que normalmente se correlacionan con los resultados más relevantes y útiles) en las listas de búsqueda.

¿Larry Page o web pages?

Existe una ambigüedad deliberada en el nombre PageRank. Aunque se aplica a la clasificación de “páginas” (pages), el nombre rinde homenaje a uno de sus creadores y fundadores de Google, Larry Page. Originalmente, el proyecto en la Universidad de Stanford se llamaba “BackRub”, debido a que el algoritmo analizaba los “backlinks” (enlaces entrantes) para determinar la relevancia.

Nuestro objetivo es establecer un método para asignar puntuaciones de importancia a cada página web dentro de la base de datos. Esto permitirá al sistema priorizar estas puntuaciones cuando un usuario realice una búsqueda y se identifique un subconjunto de páginas relevantes. El foco de este artículo está en el paso clave de definir y cuantificar la “importancia” de una página web dentro de la estructura interconectada de la web. Es importante tener en cuenta que si bien la calificación de importancia de una página web es un factor significativo, no es el único determinante de cómo se presentan los enlaces en los resultados de búsqueda.

Por supuesto, este método no es exclusivo de la web, sino que es aplicable a cualquier grafo dirigido ponderado.

4.1 El algoritmo PageRank

A lo largo de esta presentación, haremos uso de un ejemplo de juguete para comprender mejor la idea y los conceptos subyacentes.

Consideremos una red de páginas web como la del gráfico inferior, todas relacionadas con un mismo término de una búsqueda.

Las flechas de las aristas entre una web y otra indican la existencia de un enlace en la primera a la segunda. Por ejemplo, la web número 7 tiene cinco enlaces entrantes (desde las páginas 2, 4, 5, 6 y 8) y solo uno saliente (hacia la página 3).

El número en la arista del grafo que une las páginas \(i\) y \(j\) indica el número de visitantes de la página \(i\) que a continuación visitaron la página \(j\). Por ejemplo, del total de personas que visitaron la página 8, una visitó después la página 4 y tres visitaron la página 7.

La idea del buscador de Google fue presentar esa lista de 8 posibles webs relacionadas con un tema común priorizada según la importancia de cada web.

¿Cómo sabemos la importancia de cada web? La idea de Google se basaba en que la importancia se propaga: cuantas más veces se pase de una web “A” a otra web “B”, más hereda la web “B” importancia de “A”. Veamos esta idea con nuestro ejemplo sencillo.

Vamos a denotar por \(x_i\in\mathbb{R}^+\) la importancia de la web \(i\)-ésima. Este marco de trabajo nos dice que la importancia que tiene la web \(i\) proviene de las importancias de las webs que la enlazan.

En el ejemplo, la importancia de la web número 7, es decir, \(x_7\), proviene de las importancias que le aportan las webs número 2, 4, 5, 6 y 8.

Vamos a presentar en forma de matriz las conexiones entre webs (es realmente la matriz de adyacencia ponderada del grafo de antes, traspuesta) \[\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2 & 0 & 0 & 0 & 3 & 0 & 4 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0\\ 0 & 2 & 0 & 3 & 4 & 5 & 0 & 3\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\] En esta matriz, en \((i, j)\) se almacena el número de veces que se pasa del nodo \(j\) al nodo \(i\), es decir, cuántas veces el nodo \(i\) recibe un enlace desde el nodo \(j\).

Vamos a normalizar esta matriz, dividiendo cada columna por su suma. Mediante esta normalización, lo que se está expresando en el elemento \((i, j)\) es la probabilidad de transitar desde la web \(j\)-ésima a la \(i\)-ésima.

Probabilidades Reales

Nota: En casos reales, se suele conocer estas probabilidades a ciencia cierta, gracias al rastreo que hacen de nuestra actividad en internet. Esta matriz, en ese caso, reproduciría exactamente esas probabilidades de transición.

A esta matriz se la denomina matriz de transiciones y tiene la propiedad de ser estocástica por columnas, es decir, sus columnas suman uno. Esta propiedad es esencial para el desarrollo teórico del algoritmo PageRank. Una vez normalizada, la matriz de transición queda como sigue: \[M = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 3/10 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/4\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 3/10 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 2/5 & 1 & 0 & 3/4\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\]

Teniendo en cuenta esta matriz, podemos escribir las relaciones entre las importancias (los \(x_i\)) de las distintas webs: \[\left\{\begin{array}{rrrrrrrrcr} & & & & & & & 0 & = & x_{1}\\ & & & & & & & 0 & = & x_{2}\\ x_{1} & & & & + {\left.{ 3}\right/{ 10}}x_{5} & & + x_{7} & & = & x_{3}\\ & & & & & & & {\left.{ 1}\right/{ 4}}x_{8} & = & x_{4}\\ & & x_{3} & & & & & & = & x_{5}\\ & & & & {\left.{ 3}\right/{ 10}}x_{5} & & & & = & x_{6}\\ & x_{2} & & + x_{4} & + {\left.{ 2}\right/{ 5}}x_{5} & + x_{6} & & + {\left.{ 3}\right/{ 4}}x_{8} & = & x_{7}\\ & & & & & & & 0 & = & x_{8}\\ \end{array}\right.\]

Por ejemplo, la primera ecuación nos dice que la importancia de la web número 1 es 0 (ya que ninguna web enlaza a dicha página), y, mirando la ecuación correspondiente, vemos que la importancia de la web 3 proviene de la siguiente forma: toda la importancia de la web 1 más \(3/10\) de la importancia de la web 5, más toda la de la web 7, todo esto relacionado con los enlaces que van de unas a otras.

Si nos fijamos en la forma matricial del problema, estamos buscando un vector de importancias, \(\boldsymbol{x} = (x_i)\) que verifique \(M\boldsymbol{x} = \boldsymbol{x}\), es decir, un punto fijo de las importancias.

En este caso, una posible solución es: \[\boldsymbol{x} = \left( \begin{array}{c@{}} 0\\ 0\\ {\left.{ 10}\right/{ 7}}\\ 0\\ {\left.{ 10}\right/{ 7}}\\ {\left.{ 3}\right/{ 7}}\\ 1\\ 0 \end{array} \right) \]

Es común normalizar este vector de importancias para que su suma dé uno. En este caso, nos queda: \[\boldsymbol{x} = \left( \begin{array}{c@{}} 0\\ 0\\ {\left.{ 1}\right/{ 3}}\\ 0\\ {\left.{ 1}\right/{ 3}}\\ {\left.{ 1}\right/{ 10}}\\ {\left.{ 7}\right/{ 30}}\\ 0 \end{array} \right) \approx \left( \begin{array}{c@{}} 0\\ 0\\ 0.33333\\ 0\\ 0.33333\\ 0.1\\ 0.23333\\ 0 \end{array} \right) \] que también verifica \(M\boldsymbol{x} = \boldsymbol{x}\). Como resultado, vemos que las páginas más importantes son la 3 y la 5, mientras que las 1, 2, 4 y 8 tienen importancia nula.

4.2 Relación con el álgebra lineal

Según la formulación anterior del problema, tenemos que buscar un vector \(\boldsymbol{x} = (x_1, x_2, \ldots, x_n)^t\) tal que \(M\boldsymbol{x} = \boldsymbol{x}\), lo cual es equivalente a encontrar un autovector asociado al autovalor 1.

Por tanto, encontrar los vectores que lo cumplen es resolver el sistema \((M-I)\boldsymbol{x} = \boldsymbol{0}\) que, en forma matricial, se puede resolver usando Gauss-Jordan: \[\left( \begin{array}{cccccccc@{}} -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & -1 & 0 & {\left.{ 3}\right/{ 10}} & 0 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 0 & 0 & {\left.{ 1}\right/{ 4}}\\ 0 & 0 & 1 & 0 & -1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & {\left.{ 3}\right/{ 10}} & -1 & 0 & 0\\ 0 & 1 & 0 & 1 & {\left.{ 2}\right/{ 5}} & 1 & -1 & {\left.{ 3}\right/{ 4}}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \end{array} \right) \sim \left( \begin{array}{cccccccc@{}} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & - {\left.{ 10}\right/{ 7}} & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & - {\left.{ 10}\right/{ 7}} & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & - {\left.{ 3}\right/{ 7}} & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right) \] Este último sistema se escribe como: \[\left\{\begin{array}{rrrrrrrrcr} x_{1} & & & & & & & & = & 0\\ & x_{2} & & & & & & & = & 0\\ & & x_{3} & & & & - {\left.{ 10}\right/{ 7}}x_{7} & & = & 0\\ & & & x_{4} & & & & & = & 0\\ & & & & x_{5} & & - {\left.{ 10}\right/{ 7}}x_{7} & & = & 0\\ & & & & & x_{6} & - {\left.{ 3}\right/{ 7}}x_{7} & & = & 0\\ & & & & & & & x_{8} & = & 0\\ & & & & & & & 0 & = & 0\\ \end{array}\right.\] Usando este último sistema, podemos obtener las ecuaciones paramétricas de su conjunto solución (el subespacio asociado al autovalor 1) y su base: \[U = \left\{\left(\begin{array}{c} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\ x_{6}\\ x_{7}\\ x_{8} \end{array}\right) \in\mathbb{R}^8\mid\quad\begin{array}{c@{}cc} x_{1} & = & 0\\ x_{2} & = & 0\\ x_{3} & = & 10/7\alpha\\ x_{4} & = & 0\\ x_{5} & = & 10/7\alpha\\ x_{6} & = & 3/7\alpha\\ x_{7} & = & \alpha\\ x_{8} & = & 0 \end{array} ,\quad\alpha\in\mathbb{R}\right\}\quad = \quad\mathcal{L}\left\{\left( \begin{array}{c@{}} 0\\ 0\\ {\left.{ 10}\right/{ 7}}\\ 0\\ {\left.{ 10}\right/{ 7}}\\ {\left.{ 3}\right/{ 7}}\\ 1\\ 0 \end{array} \right) \right\}\]

Podemos observar por tanto que llegamos a la solución propuesta en el apartado anterior. Es decir, hemos llegado a un subespacio que determina la importancia de cada nodo dentro del grafo. Tomamos entonces un vector cuya suma de las componentes sea 1 dentro de ese subespacio y tenemos las puntuaciones de importancia que queríamos.

¿Seguro que el 1 es autovalor?

Bajo condiciones suficientemente generales en la práctica, podemos asegurar que 1 es autovalor. Es fundamental que la suma por columnas sea 1. Más aún: \(\lambda = 1\) es el mayor autovalor de la matriz \(M\) (Teorema de Perron-Frobenius).

¿Y si la dimensión del subespacio es > 1?

Si el subespacio asociado tiene dimensión mayor que 1, no podríamos obtener un único autovector de probabilidad. Existe una estrategia (la que implementa Google), que permite asegurar que la dimensión del subespacio asociado al autovalor 1 es exactamente uno.

4.3 ¿Cómo hacerlo en R?

Una vez definida la matriz \(M\) de transiciones, es necesario, como hemos comentado antes, normalizar para que las columnas sumen 1. A modo de ayuda, copio aquí un código que puede ayudar a realizar esta normalización:

M <- scale(M, 
           center = FALSE, 
           scale = colSums(M))

Una vez que tenemos esta matriz de transición, existen múltiples librerías que permiten calcular valores y vectores propios. De hecho, el propio R base tiene la función eigen() que calcula tanto los autovalores como los autovectores de una matriz dada (teniendo en cuenta que, por defecto, va a trabajar en \(\mathbb{C}\)).

Internamente, la mayoría de librerías utilizan técnicas numéricas iterativas.

Como vimos en el Capítulo de Autovalores, el método de la potencia es el algoritmo estándar para encontrar el autovalor dominante (y su autovector asociado) de una matriz. Dado que en nuestro caso sabemos (por Perron-Frobenius) que el mayor autovalor es \(\lambda=1\), este método es ideal y es, de hecho, la base del algoritmo original de Google.

Podemos usar la misma función powerMethod de la librería matlib que introdujimos en el capítulo anterior:

library(matlib)
resultado <- powerMethod(M)

Podemos ver el autovalor determinado:

resultado$value

[1] 1

y el autovector correspondiente:

resultado$vector

       [,1]
1 0.0000000
2 0.0000000
3 0.6225730
4 0.0000000
5 0.6225725
6 0.1867718
7 0.4358011
8 0.0000000

En nuestro caso, como siempre, queremos un vector cuya componentes sumen 1, así que hacemos lo siguiente:

resultado$vector / sum(resultado$vector)

        [,1]
1 0.00000000
2 0.00000000
3 0.33333345
4 0.00000000
5 0.33333317
6 0.09999996
7 0.23333342
8 0.00000000

que es prácticamente igual al vector de importancias \(\boldsymbol{x}\) que hallamos en la sección del algoritmo PageRank.

4.4 Problemas en la web real

Hasta ahora hemos asumido un grafo ideal. Sin embargo, en la web real existen estructuras que rompen la lógica básica del PageRank si no se tratan.

4.4.1 Callejones sin salida (dead ends)

Son páginas que no tienen enlaces salientes.

Si el navegante llega a C, no tiene a dónde ir. Matemáticamente, la columna correspondiente en la matriz de transición tendría ceros, y la matriz dejaría de ser estocástica (sus columnas no suman 1). La importancia se “fugaría” del sistema en cada iteración hasta llegar a 0.

4.4.2 Trampas de araña (spider traps)

Son grupos de páginas que se enlazan entre sí pero no al resto de la web.

Aquí, una vez que el navegante entra en el bucle 3-4, nunca sale. Estos nodos acumularían toda la importancia del grafo, absorbiéndola del resto (Rank Sinks).

4.5 El factor de amortiguación (damping factor)

Para solucionar esto, los creadores de Google, Brin y Page, introdujeron el factor de amortiguación (\(d\)).

La idea es modelar el comportamiento de un usuario que navega aleatoriamente: la mayoría de las veces sigue un enlace (con probabilidad \(d\)), pero ocasionalmente se “aburre” y salta a cualquier otra página aleatoria de la web (con probabilidad \(1-d\)).

El Navegante Aleatorio

El modelo del “Random Surfer” es una metáfora intuitiva del comportamiento humano en la web. Supone que un usuario nunca se queda atrapado en una web infinitamente (trampas de araña), sino que después de unos cuantos clics, decide escribir una nueva dirección en la barra del navegador. El factor de amortiguación \(d=0.85\) implica que, en promedio, un usuario sigue unos 6 enlaces antes de “saltar” a una página al azar.

La Matriz de Google (\(G\)) se define entonces como:

\[G = d \cdot M + (1-d) \cdot \frac{1}{n} J\]

En esta ecuación, \(M\) representa la matriz de transición original (previamente corregida para manejar los “dead ends”), mientras que \(J\) es una matriz conformada exclusivamente por unos de tamaño \(n \times n\). El parámetro \(d\) es el factor de amortiguación, cuyo valor estándar se establece típicamente en 0.85.

Esta nueva matriz \(G\) tiene propiedades matemáticas maravillosas (es estocástica, irreductible y primitiva), lo que garantiza por el Teorema de Perron-Frobenius que existe un único autovector de probabilidad con autovalor 1, y que el método de la potencia siempre converge a él.

4.5.1 Implementación en R

Vamos a modificar nuestro ejemplo para incluir este factor de amortiguación \(d=0.85\).

# Factor de amortiguación estándar
d <- 0.85
n <- nrow(M)

# Matriz de 'teletransportación' (probabilidad uniforme de saltar a cualquier nodo)
J <- matrix(1, nrow = n, ncol = n)

# Matriz Google
G <- d * M + (1 - d) * (1/n) * J

# Calculamos el PageRank con la matriz G usando el método de la potencia
resultado_google <- powerMethod(G)

# Autovector normalizado (PageRank final)
pagerank_scores <- resultado_google$vector / sum(resultado_google$vector)
pagerank_scores

        [,1]
1 0.01875000
2 0.01875000
3 0.30960493
4 0.02273438
5 0.28191450
6 0.09063817
7 0.23885802
8 0.01875000

Vemos que las puntuaciones cambian ligeramente, pero el orden de importancia suele mantenerse en estructuras estables. Este vector pagerank_scores sería el utilizado para ordenar los resultados de búsqueda.

4.6 Ejercicios adicionales

Ejercicio 4.1 (El Mercado de Smartphones (Cadenas de Markov)) Tres marcas (A, B y C) se reparten el mercado. Cada año, los clientes cambian de marca según esta lógica:

De los que tienen A: 70% se queda, 20% pasa a B, 10% pasa a C.
De los que tienen B: 10% pasa a A, 80% se queda, 10% pasa a C.
De los que tienen C: 10% pasa a A, 10% pasa a B, 80% se queda.

Construye la matriz de transición \(P\) (asegúrate de que sea estocástica por columnas).
Esta matriz tiene un autovalor \(\lambda=1\). Encuentra el autovector asociado y normalízalo para que sume 1.
¿Cuál será la cuota de mercado de cada marca a largo plazo (el estado estacionario)?
Verifica el resultado elevando la matriz \(P\) a una potencia alta (ej. \(P^{50}\)) y multiplicando por cualquier cuota de mercado inicial.

Ejercicio 4.2 (Influencia en Citas Académicas) Un consejo científico quiere medir la influencia de 4 investigadores (A, B, C y D) basándose en cómo se citan entre ellos:

A cita a B y C.
B cita a C.
C cita a A.
D cita a C.

Dibuja el grafo dirigido correspondiente a estas citas.
Construye la matriz de adyacencia \(M\) (donde \(M_{ij}=1\) si \(j\) cita a \(i\)).
Identifica si existe algún “callejón sin salida” (dead end) y corrígelo si es necesario (asumiendo que desde un nodo sin citas se puede saltar a cualquier otro con probabilidad \(1/n\)).
Calcula la Matriz de Google \(G\) usando un factor de amortiguación \(d=0.85\).
Calcula el vector de PageRank. ¿Quién es el investigador más influyente según este modelo? ¿Coincide con quien tiene más citas totales (grado de entrada)?