Análisis de Grafos Grandes con PageRank
Análisis de Grafos Grandes con PageRank' can be condensed to 'Análisis de Grafos Grandes y PageRank'.
Descubre cómo el motor de búsqueda de Google clasifica los documentos basándose en su estructura de enlaces
La clasificación es un problema importante en el aprendizaje automático. Dado un conjunto de documentos, el objetivo es ordenarlos en un orden específico basado en ciertos criterios. La clasificación se utiliza ampliamente en sistemas de recuperación de información para ordenar los resultados de búsqueda o en sistemas de recomendación para filtrar contenido que potencialmente será interesante para un usuario en particular.
Según un problema y objetivo dados, existen una gran cantidad de algoritmos de clasificación. El que vamos a estudiar en este artículo se llama PageRank. Su objetivo principal es clasificar un conjunto de documentos (páginas web) utilizando la información sobre su conectividad. La clasificación asignada a cada página web indica su importancia: cuanto mayor sea la clasificación, mayor será la importancia. El algoritmo se basa en dos suposiciones que vamos a analizar en la siguiente sección.
Suposiciones
Podemos definir el término “importancia” de una página web haciendo dos suposiciones.
La importancia de una página web es alta si muchas otras páginas web apuntan a ella.
Imagina que tenemos un artículo de investigación popular y muchos otros artículos enlazan a él utilizando citas o resultados de él. En principio, tiene sentido asignarle una gran importancia a este artículo. Por otro lado, si hay una página web desconocida sin enlaces hacia ella desde otros recursos, parece lógico asignarle poca importancia a la página.
En realidad, también deberíamos tener en cuenta la calidad de los enlaces entrantes.
La importancia de una página web es proporcional a la importancia de las páginas web que apuntan a ella.
Si una página es citada originalmente por un artículo de alta calidad en Wikipedia, entonces dicho enlace debería tener un mayor peso. Por el contrario, cuando un recurso totalmente desconocido apunta a otra página web, normalmente no debería tener una importancia alta.
Definición formal
Digamos que la importancia de un nodo es igual a la suma de los pesos de los enlaces entrantes.
Imagina un nodo i con una importancia rᵢ que tiene k enlaces salientes. ¿Cómo podemos determinar el peso de cada enlace? El enfoque más directo es tomar la importancia del nodo y dividirla equitativamente entre todos los enlaces salientes. De esta manera, cada enlace saliente recibirá el peso de rᵢ / k.
Dado un grafo de n páginas web, podemos crear un sistema de n ecuaciones lineales para encontrar los pesos del grafo. Sin embargo, dicho sistema puede tener un número infinito de soluciones. Es por eso que debemos agregar otra restricción que imponga una solución única. Por cierto, PageRank agrega la condición normalizada de que la suma de la importancia de todos los nodos sea igual a 1.
Hemos encontrado una solución pero no es escalable. Incluso con la eliminación gaussiana, terminamos con una complejidad de O(n³). Teniendo en cuenta que el número de páginas web analizadas n puede alcanzar miles de millones, necesitamos encontrar un enfoque más eficiente.
Primero que todo, simplifiquemos la notación. Para esto, introducimos la matriz cuadrada de adyacencia G que contendrá los pesos de los enlaces para cada par de páginas web enlazadas (si dos páginas web no están enlazadas, pondremos 0 en el elemento correspondiente de la matriz). Más formalmente:
![Definición de un elemento de la matriz G[j][i]](https://miro.medium.com/v2/resize:fit:640/format:webp/1*xB7oRh5508uhOkBiRjSjlg.png)
A la matriz G se le llama estocástica porque cada una de sus columnas suma 1.
A continuación, definimos el vector de rango r cuyo i-ésimo elemento es igual al rango (importancia) de la página i. La suma de todos los elementos de este vector también es igual a 1. Nuestro objetivo final es encontrar los valores de este vector r.
Ecuación de PageRank
Veamos qué sucederá si multiplicamos la matriz G por el vector r. Basándonos en el ejemplo con el grafo de la sección anterior, ¡podemos ver que da como resultado el mismo vector r!
¿Por qué sucede esto? ¿Es solo una coincidencia? Recuerda que la i-ésima fila de la matriz G contiene los pesos de todos los enlaces de entrada a la página i. Cuando multiplicamos el j-ésimo elemento de la i-ésima fila por r[j], en realidad obtenemos el componente rj / d[j]out, la importancia que fluye desde el nodo j hacia i. Si no hay enlace entre los nodos i y j, entonces el componente respectivo se establece en 0. Lógicamente, el resultado final de la multiplicación de la i-ésima fila por el vector r será igual a la suma de todas las importancias que fluyen desde cualquier nodo conectado del grafo hacia el nodo i. Según la definición, este valor es igual al rango del nodo i. En general, podemos escribir la siguiente ecuación:
Por lo tanto, nuestro objetivo es encontrar un vector r que, al ser multiplicado por la matriz de entrada G, permanezca igual.
Vectores propios
Podemos encontrar la solución a la ecuación anterior revisando la teoría de los vectores propios del álgebra lineal. Dada una matriz A, el vector v se llama vector propio si existe un número α que satisface la siguiente ecuación:
El número α se llama valor propio. Podemos notar que la ecuación de PageRank corresponde a la ecuación de valor propio donde A = G, v = r y α = 1. Normalmente, cualquier matriz cuadrada tiene varios valores propios y vectores propios, pero dado que nuestra matriz G es estocástica, la teoría afirma que su valor propio más grande es igual a 1.
Iteración de potencia
Una de las formas más populares de encontrar los autovectores de una matriz es el método de iteración de potencia. Consiste en inicializar un vector inicial r con algunos valores (usaremos 1 / n donde n es el número de páginas web), luego calcular constantemente el valor de G * r y asignar este valor nuevamente a r. Si en alguna iteración la distancia entre los vectores r y G * r es menor que un umbral ε determinado, detenemos el algoritmo ya que ha convergido exitosamente.
En el ejemplo anterior podemos ver que al establecer ε en 0.0005, el algoritmo converge correctamente en solo 9 iteraciones:
Obviamente, este es solo un ejemplo ilustrativo, pero en la práctica, este método funciona muy bien incluso para un mayor número de variables.
Caminata aleatoria
Imagina a un surfista (caminante) en cualquier nodo del grafo en el momento t. Denotemos por p(t) al vector cuyo componente i-ésimo representa la probabilidad de que en el momento t el surfista se encuentre en el nodo i. Luego, el surfista elige aleatoriamente (con igual probabilidad) otro nodo vinculado al actual y se mueve allí en el momento t + 1. En última instancia, queremos encontrar el vector de distribución p(t + 1) en el momento t + 1.
Podemos observar que la probabilidad de que el surfista aparezca en un nodo i en el momento t + 1 es la suma de las probabilidades (sobre todos los nodos vinculados a i) de que el surfista estuviera previamente en un nodo adyacente j multiplicado por la probabilidad de moverse del nodo j al nodo i.
- Ya conocemos la probabilidad de que el surfista aparezca en el nodo j en el momento t: p(t)[j].
- La probabilidad de moverse del nodo j al nodo i es igual a G[j][i].
Al sumar estas probabilidades, obtenemos el valor de p(t + 1)[i]. Para encontrar el valor de p(t + 1) para todos los nodos del grafo, podemos escribir la misma ecuación en forma matricial:
¡Esta ecuación tiene exactamente la misma forma que la que obtuvimos para el PageRank antes! Esto significa que estos dos problemas tienen la misma solución e interpretación.
En algún momento, el vector de distribución p(t) convergerá: p(t + 1) = M * p(t) = p(t). El vector convergido p(t) en este caso se denomina distribución estacionaria. En todos los momentos siguientes, la probabilidad de residir en cualquier nodo dado no cambia.
El puntaje de PageRank de un nodo es igual a la probabilidad de que el surfista se encuentre en este nodo en el futuro al caminar aleatoriamente por el grafo.
Convergencia
El proceso descrito de caminar por todo el grafo a menudo se denomina “cadenas de Markov”. Existe un teorema en la teoría de las cadenas de Markov que establece:
Bajo ciertas condiciones en la estructura del grafo, la distribución estacionaria es única y se puede alcanzar con cualquier distribución de probabilidad inicial en el momento t = 0.
En la siguiente sección, profundizaremos en las condiciones que deben cumplirse para lograr una convergencia única. Resulta que no todos los grafos pueden lograr una convergencia única.
Principalmente, existen 2 tipos de casos que queremos evitar a toda costa.
Caminos sin salida
Los nodos que no tienen enlaces de salida se llaman caminos sin salida. El problema con este tipo de nodos es que debido a ellos, la importancia total se pierde en la red. Aquí tienes un ejemplo:
Trampa de araña
Un grupo de nodos forma una trampa de araña si no tienen enlaces de salida a otros nodos fuera de este grupo. Básicamente, una vez allí, es imposible salir de este grupo de nodos. Las trampas de araña llevan a los siguientes problemas:
- El algoritmo nunca converge.
- El grupo de nodos que forma una trampa de araña absorbe toda la importancia del grafo. Como resultado, estos nodos tienen una importancia muy alta mientras que otros nodos tienen una importancia igual a 0.
El primer problema se ilustra en la siguiente figura:
La absorción de importancia se demuestra en la siguiente figura. Aunque puede no parecer un problema grave en el ejemplo sencillo a continuación, imagina una red de páginas web con millones de páginas web donde varias de ellas forman una trampa de araña. Como consecuencia, estas varias páginas distribuirán toda la importancia disponible mientras que la importancia de todas las demás páginas web se establecerá en 0. Obviamente, esto no es lo que normalmente queremos en la vida real.
Teletransportes
Una de las soluciones propuestas por Google es agregar la siguiente condición antes de cada movimiento del surfista:
- Con probabilidad β, moverse a otro nodo enlazado.
- Con probabilidad (1 — β), moverse a un nodo aleatorio (a través de un teletransporte).
El parámetro β se denomina el factor de amortiguamiento. Los autores del algoritmo original de PageRank recomiendan elegir el valor de β = 0.85, lo que significa que en promedio después de 5 transiciones el surfista saltará aleatoriamente a otro nodo. La idea es que si el surfista cae en una trampa de araña, eventualmente saldrá de allí a través de un teletransporte.
El diagrama a continuación muestra cómo los teletransportes pueden ayudar a resolver el problema de la trampa de araña. Si el surfista camina hacia el nodo c, se quedará allí para siempre. La introducción de teletransportes (líneas azules) ayuda a eliminar este problema garantizando que después de algún tiempo el surfista tendrá que caminar hacia otro nodo aleatorio.
Sin embargo, para los nodos sin salida, necesitamos modificar ligeramente el enfoque. A partir de uno de los ejemplos anteriores, sabemos que los callejones sin salida provocan fugas de importancia en un grafo. Este fenómeno se puede observar durante el método de iteración de potencia, cuando el vector de clasificación se llena de ceros debido a una columna de cero correspondiente en la matriz inicial G. En última instancia, lo que podemos hacer es lo siguiente:
Cuando el surfista llega a un nodo sin salida, inmediatamente debe saltar a un nodo aleatorio (con igual probabilidad) del grafo.
De hecho, podemos modificar la matriz inicial G para satisfacer esta afirmación: simplemente necesitamos reemplazar los ceros por 1 / n en lugar de todos los elementos de las columnas de todos los nodos sin salida de la matriz G. El ejemplo a continuación demuestra este principio.
El nodo c es un nodo sin salida con una columna correspondiente de ceros en la matriz G. Agregar n = 3 teletransportaciones desde c a todos los nodos del grafo impone una probabilidad igual p = 1 / 3 de moverse desde c hacia cualquier nodo. Para tener esto en cuenta, llenamos la columna de la matriz G correspondiente al nodo c con valores de 1 / 3.
Podemos observar que después de agregar las teletransportaciones, la suma de todas las columnas de la matriz es ahora igual a 1. En otras palabras, la matriz G se vuelve estocástica. Esta es una propiedad esencial que se utilizará más adelante.
Condición de convergencia
Existe un teorema crucial de la teoría de las cadenas de Markov que define la condición de convergencia.
Para cualquier vector de inicio, la matriz de transición G converge a un vector de distribución estacionaria positiva única r si la cadena correspondiente a G es estocástica, aperiódica e irreducible.
Recordemos las tres últimas propiedades en este teorema y verifiquemos si las teletransportaciones introducidas resuelven los problemas anteriores.
Una cadena G se llama estocástica si la suma de cada una de sus columnas es igual a 1.
Como observamos anteriormente, agregar teletransportaciones a los nodos sin salida elimina las columnas de ceros en la matriz y hace que la suma de todas sus columnas sea igual a 1. La condición ya se cumple.
Una cadena G se llama periódica si existe un número k > 1 tal que la longitud del camino entre cualquier par de nodos es siempre un múltiplo de k. De lo contrario, la cadena se llama aperiódica.
Esta condición significa que cualquier retorno al mismo estado debe ocurrir en múltiplos de k veces. En el caso de la aperiodicidad, el retorno ocurre en tiempos irregulares. Básicamente, la condición se refiere al problema de la trampa de araña. Dado que ya hemos resuelto el problema de las trampas de araña agregando teletransportaciones, la cadena G es aperiódica.
Una cadena G se llama irreducible si la probabilidad de transicionar desde cualquier nodo a cualquier otro nodo siempre es mayor que 0.
Esta condición implica que siempre existe un enlace entre cualquier par de nodos, por lo que es imposible quedar atrapado en algún nodo. En otras palabras, la matriz G debe consistir en todos los elementos no nulos. Veremos en la siguiente sección cómo se cumplirá esta condición conectando todos los nodos del grafo.
Modificando el algoritmo
El algoritmo de PageRank propuesto por Google toma la matriz inicial G y la ajusta agregando teletransportaciones desde los nodos sin salida a otros nodos. Esto asegura la estocasticidad. Para garantizar la aperiodicidad e irreducibilidad, luego agrega la condición descrita anteriormente a cada nodo:
- Con probabilidad β, moverse a otro nodo enlazado.
- Con probabilidad (1 — β), moverse a un nodo aleatorio.
Matemáticamente, esto resulta en la siguiente ecuación de rango para cada nodo:
Podemos transformar esta ecuación en forma de matriz:
Veamos el grafo modificado y la matriz de transición correspondiente R a partir de uno de los ejemplos anteriores:
Aumento de la eficiencia
El único problema que nos queda es cómo almacenar la matriz de transición R. Recuerda que R es una matriz cuadrada de tamaño n x n donde n es el número de páginas web. ¡Actualmente, Google tiene más de 25 mil millones de páginas web! La matriz R no tiene ningún cero, por lo que es densa, lo que significa que debemos almacenarla por completo. Supongamos que cada elemento de la matriz requiere 4 bytes para ser almacenado. El tamaño total de memoria requerido para almacenar la matriz R es igual a (25 * 10⁹)² * 4 (bytes) ~ 3 * 10²¹ (bytes). ¡Este es un tamaño de memoria gigantesco! Necesitamos idear otro enfoque para reducir al menos varios órdenes.
En primer lugar, simplemente podemos observar que agregar teletransportes es equivalente a reducir los elementos iniciales de la matriz G en (1 — β)% y distribuirlos de manera uniforme en cada nodo. Teniendo esto en cuenta, podemos transformar la ecuación de la matriz en otra formato:
Veamos la última ecuación obtenida. G es la matriz de enlaces inicial con la mayoría de los elementos iguales a 0. ¿Por qué es así? En realidad, si tomas cualquier página web, probablemente contenga como máximo unas pocas docenas de enlaces a otras páginas web. Teniendo en cuenta que hay más de 25 mil millones de páginas web, obtenemos que el número relativo de enlaces totales en comparación con el número de páginas web es extremadamente pequeño. Por lo tanto, hay muchos ceros en G, por lo que G es dispersa.
Almacenar matrices dispersas requiere mucho menos memoria que las matrices densas. Supongamos que cada página web en promedio enlaza con otras 40 páginas. El número total de bytes requeridos para almacenar la matriz G ahora se convierte en 25 * 10⁹ * 40 (bytes) = 10¹² (bytes) = 1 (TB). Resulta que solo necesitamos 1 terabyte para almacenar G. ¡Comparado con lo que teníamos anteriormente, esto es una mejora fabulosa!
De hecho, en cada iteración, solo necesitamos calcular la multiplicación de la matriz G por el vector r, multiplicarlo por β y agregar una constante (1 — β) / n a cada elemento del vector resultante.
También debemos tener en cuenta que si la cadena inicial G contiene nodos sin salida, entonces la suma del vector r en cada iteración será menor que 1. Para lidiar con esto, es suficiente normalizarlo, de modo que todas las componentes del vector sumen 1.
Algoritmo completo
En la figura a continuación se muestra la versión completa del algoritmo de PageRank. En cada iteración, la actualización de los rangos se realiza en 2 etapas. La primera etapa incluye solo la actualización según la matriz inicial G. Luego sumamos los componentes del vector de rango en la variable s. De esta manera, el valor de (1 — s) es el valor por el cual se redujo el rango de entrada total de un solo nodo. Para compensar esto, en la segunda etapa, tenemos en cuenta los teletransportes y los agregamos desde un nodo a todos los nodos con el mismo valor de (1 — s) / n.
Conclusión
En este artículo, hemos analizado diferentes formulaciones del algoritmo PageRank para finalmente llegar a su versión optimizada. A pesar de la existencia y evolución de otros métodos para clasificar los resultados de búsqueda, PageRank sigue siendo el algoritmo más eficiente entre otros que funcionan bajo el capó del motor de búsqueda de Google.
Referencias
La estructura lógica de este artículo se basa en la conferencia de la Universidad de Stanford sobre grafos grandes.
- Análisis de grafos grandes: Análisis de enlaces, PageRank
- Minería de conjuntos de datos masivos | Jure Leskovec, Anand Rajaraman, Jeff Ullman
- PageRank: Parado sobre los hombros de gigantes
Todas las imágenes, a menos que se indique lo contrario, son del autor
