Centralidad PageRank
- Propuesto por
- Page, Brin, Motwani & Winograd
- Año
- 1999
- Tipo
- Iterative link-based centrality algorithm
- Familia
- Centrality
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
PageRank es un algoritmo de centralidad basado en enlaces que asigna una puntuación de importancia a cada nodo en un grafo dirigido, midiendo cuántos nodos de alta calidad apuntan hacia él.
Introducido por Larry Page, Sergey Brin, Rajeev Motwani y Terry Winograd en la Universidad de Stanford en 1999, se convirtió en la base matemática del motor de búsqueda Google y sigue siendo uno de los algoritmos más influyentes en la ciencia de redes y la recuperación de información.
La intuición detrás del método
Imagínese un surfista web aleatorio que hace clic en enlaces al azar, saltando ocasionalmente a una página completamente aleatoria en lugar de seguir un enlace. La fracción de tiempo que este surfista pasa en cada página, después de infinitos clics, es el PageRank de esa página. Una página visitada a menudo —porque muchas páginas populares enlazan a ella— recibe una puntuación alta. El factor de amortiguación (típicamente 0.85) modela la probabilidad de continuar haciendo clic en lugar de saltar.
Historia
PageRank fue desarrollado en la Universidad de Stanford por Larry Page y Sergey Brin como el mecanismo de clasificación central de su proyecto de búsqueda BackRub, que se convirtió en Google en 1998. El informe técnico fundamental, coescrito con Rajeev Motwani y Terry Winograd, se publicó en 1999. El algoritmo popularizó el uso de la centralidad basada en autovectores en redes dirigidas a gran escala e inspiró directamente algoritmos posteriores de análisis de enlaces, incluidos HITS y TrustRank.
Cuándo usarlo
PageRank es apropiado cuando se necesita clasificar nodos en un grafo dirigido por importancia estructural global, especialmente cuando la dirección de la arista codifica el respaldo o la influencia (hipervínculos, citas, seguimientos sociales). Asume que el grafo puede modelarse como una cadena de Markov y requiere un componente conectado o fuertemente conectado para una convergencia limpia. Es menos adecuado para redes no dirigidas donde se pueden preferir HITS o la centralidad de intermediación, y puede ser sensible al spam de enlaces o a un grado de entrada artificialmente inflado.
Limitaciones y consideraciones
- Requiere un grafo dirigido; la aplicación a redes no dirigidas necesita opciones de convención
- La velocidad de convergencia depende del hueco espectral de la matriz de transición y puede ser lenta para grafos mal conectados
- Sensible a la elección del factor de amortiguación d; diferentes valores pueden alterar sustancialmente las clasificaciones
- Vulnerable a la manipulación de granjas de enlaces y a enlaces entrantes artificialmente construidos
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Fundamento probabilístico principista a través del modelo de cadena de Markov del surfista aleatorio
- Escala a grafos muy grandes mediante productos de matrices dispersas vectoriales e iteración de potencias
- Captura la topología global del grafo, recompensando a los nodos respaldados por otros nodos de alta puntuación
- Ampliamente validado en dominios de redes web, de citas, biológicas y sociales
Aplicaciones
- Clasificación de motores de búsqueda web: ordenación de resultados de búsqueda por la autoridad global de las páginas web
- Análisis de citas académicas: identificación de artículos o revistas influyentes en redes de literatura científica
- Medición de influencia en redes sociales: clasificación de usuarios por el prestigio de sus seguidores
- Análisis de redes biológicas: identificación de proteínas o genes clave en redes de interacción de proteínas y regulación génica
- Sistemas de recomendación: propagación de señales de preferencia a través de grafos bipartitos de usuarios-elementos
Cómo funciona
Cómo funciona
Cada nodo del grafo comienza con una puntuación PageRank igual de 1/N, donde N es el número total de nodos. Esta inicialización uniforme asegura que ningún nodo tenga una ventaja artificial y proporciona una distribución de probabilidad válida en toda la red antes de la primera iteración.
Fórmula
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}Se construye una matriz de transición estocástica por columnas M a partir de la estructura de adyacencia del grafo. Cada entrada M_ij es igual a 1 dividido por el grado de salida del nodo j si existe una arista de j a i, y cero en caso contrario. Los nodos colgantes (sin aristas salientes) se suelen manejar redistribuyendo su puntuación uniformemente entre todos los nodos.
Fórmula
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}El vector PageRank se actualiza iterativamente utilizando la fórmula del surfista aleatorio. Con el factor de amortiguación d (por defecto 0.85), cada nodo recibe una probabilidad base de teletransporte (1-d)/N más d veces la suma ponderada de las puntuaciones aportadas por todos los nodos que enlazan a él. Este paso se repite hasta que las puntuaciones se estabilizan.
Fórmula
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}Después de cada iteración, la norma L1 del cambio en el vector de puntuaciones se compara con una pequeña tolerancia epsilon (por ejemplo, 1e-6). Cuando el cambio cae por debajo de este umbral, el algoritmo ha convergido y el vector de puntuaciones actual se devuelve como la distribución PageRank final.
Fórmula
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonErrores comunes
- Ignorar los nodos colgantes (nodos sin aristas salientes) puede romper la propiedad estocástica de la matriz de transición y causar puntuaciones incorrectas
- Usar PageRank en grafos no dirigidos sin convertir a un modelo de transición simétrico puede producir estimaciones de centralidad engañosas
- Establecer la tolerancia de forma demasiado laxa conduce a una convergencia prematura; de forma demasiado estricta aumenta el cálculo sin cambios significativos en las puntuaciones
- Interpretar PageRank como una métrica de importancia absoluta en lugar de una clasificación relativa dentro de un contexto de grafo específico
Preguntas frecuentes
¿Qué representa el factor de amortiguación d y cómo se debe elegir?
El factor de amortiguación d (típicamente 0.85) es la probabilidad de que el surfista aleatorio siga un enlace en lugar de teletransportarse a un nodo aleatorio. Los valores cercanos a 1 hacen que el algoritmo sea más sensible a la estructura del grafo, pero más lento de converger y más propenso a sumideros de clasificación; los valores cercanos a 0 se aproximan a una clasificación uniforme. El valor 0.85 fue validado empíricamente por Page y Brin para el grafo web y es el valor predeterminado estándar.
¿En qué se diferencia PageRank de la centralidad de grado?
La centralidad de grado cuenta solo el número directo de enlaces entrantes a un nodo, tratando todas las fuentes por igual. PageRank pondera cada enlace entrante por la puntuación del nodo enlazante, por lo que un respaldo de un nodo de alta clasificación contribuye más que uno de un nodo de baja clasificación. Esta definición recursiva captura la estructura global del grafo en lugar de solo la conectividad local.
¿Se puede aplicar PageRank a grafos no dirigidos?
Sí, pero con advertencias. Un grafo no dirigido debe convertirse a una representación dirigida reemplazando cada arista no dirigida por dos aristas dirigidas. Las puntuaciones PageRank resultantes son entonces iguales a una función del grado del nodo, reduciendo el algoritmo a una centralidad de grado ponderada. Para redes no dirigidas, medidas de centralidad alternativas como la centralidad de autovectores o la centralidad de intermediación suelen ser más informativas.
Métodos relacionados
Fuentes
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
Abrir referencia de la publicaciónCopiado.