Saltar al contenido
Volver a los resultados

PageRank Ponderado

Propuesto por
Xing, W. & Ghorbani, A.
Año
2004
Tipo
Centrality measure / ranking algorithm
Familia
Network science

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

El PageRank Ponderado extiende el algoritmo clásico de PageRank a redes donde los enlaces tienen diferentes fuerzas o frecuencias, distribuyendo la importancia proporcionalmente a los pesos de los enlaces tanto entrantes como salientes, en lugar de tratar todos los enlaces por igual. Esto lo hace sustancialmente más informativo que el PageRank binario en cualquier red donde la fuerza de la conexión sea relevante.

La intuición detrás del método

El PageRank clásico trata cada hipervínculo o conexión de manera idéntica: un nodo obtiene el mismo prestigio de una conexión débil que de una fuerte. El PageRank Ponderado corrige esto escalando cada "voto" por el peso relativo del enlace. Un nodo que recibe muchos enlaces entrantes de gran peso de nodos ya importantes asciende más alto en la clasificación, mientras que un nodo con numerosas pero débiles conexiones permanece modesto. Esto refleja cómo la influencia se acumula realmente en la mayoría de las redes del mundo real, donde la frecuencia de interacción o el volumen de transacciones señalan la verdadera importancia.

Historia

PageRank fue introducido por Brin y Page en 1998 como la base de Google Search, tratando todos los hipervínculos como votos iguales. El PageRank Ponderado fue formalizado por Xing y Ghorbani en 2004, extendiendo el algoritmo para asignar la distribución de rango proporcionalmente a los pesos de los enlaces, basándose en fracciones de peso de entrada y peso de salida. Desde entonces, se ha aplicado en análisis de citas, bioinformática, análisis de redes sociales y sistemas de recomendación, donde la fuerza del enlace es un proxy significativo de la influencia.

Cuándo usarlo

Utilice PageRank Ponderado cuando su red tenga pesos de arista significativos y necesite una clasificación de importancia global y consciente del flujo de los nodos. Es ideal para redes de citas con recuentos de co-citas, grafos web con volúmenes de tráfico, redes de interacción biológica con niveles de expresión, redes sociales con frecuencias de interacción y redes de transacciones financieras. Prefiera PageRank Ponderado sobre PageRank binario siempre que ignorar la fuerza de los enlaces tergiversaría el flujo de influencia. Evítelo cuando los pesos de los enlaces no sean fiables o se asignen arbitrariamente, cuando la red sea muy dispersa y los pesos sean mayormente binarios (el PageRank simple es suficiente), o cuando necesite una medida de centralidad puramente local como el grado ponderado. No es apropiado para redes no dirigidas donde la dirección del flujo es conceptualmente insignificante.

Limitaciones y consideraciones

  • Requiere que los pesos de los enlaces sean significativos y se midan de forma fiable; los pesos ruidosos o arbitrarios degradan la calidad de la clasificación.
  • El factor de amortiguación (d) es un parámetro libre; el 0.85 convencional puede no ser óptimo para redes no web.
  • Sensible al esquema de normalización de pesos elegido; los resultados pueden diferir si los pesos de entrada y salida se combinan de manera diferente.
  • No distingue entre diferentes tipos de enlaces; un modelo de peso único puede colapsar distinciones estructurales importantes.
  • La convergencia puede ser lenta en redes muy grandes y densas sin implementaciones eficientes de matrices dispersas.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Incorpora la fuerza del enlace directamente en la propagación de la importancia, lo que produce clasificaciones más realistas que el PageRank binario en redes ponderadas.
  • Captura el prestigio global de toda la red en lugar de solo la conectividad local.
  • Preserva el mecanismo de teletransportación de PageRank, lo que lo hace robusto frente a nodos colgantes y componentes desconectados cuando se corrige.
  • Escala a redes grandes mediante una computación iterativa eficiente; las operaciones de matrices dispersas mantienen la memoria manejable.
  • Fácilmente interpretable: una puntuación alta significa que un nodo recibe un respaldo fuerte y ponderado de otros nodos con puntuaciones altas.

Aplicaciones

  • Identificar artículos o autores influyentes en redes ponderadas de citas y coautorías.
  • Clasificar páginas web o documentos cuando se dispone de volúmenes de tráfico de hipervínculos o tasas de clics.
  • Detectar proteínas o genes clave en redes de interacción biológica ponderadas.
  • Priorizar nodos en redes de transacciones financieras por el flujo de volumen de transacciones.
  • Clasificar usuarios o contenido en grafos ponderados de interacción en redes sociales.
  • Construir sistemas de recomendación donde las frecuencias de co-ocurrencia de ítems sirven como pesos de los enlaces.

Cómo funciona

Cómo funciona

1

Represente la red como un grafo donde cada arista tiene un peso numérico que refleja la fuerza del vínculo, como la frecuencia de interacción, el volumen de transacciones, el recuento de coautorías o la puntuación de similitud. El algoritmo requiere que estos pesos sean no negativos; los pesos negativos deben transformarse antes del análisis.

2

Para cada arista dirigida del nodo v al nodo u, calcule dos factores de peso: un factor de peso de entrada que normaliza el peso de la arista por el peso total de entrada de u, y un factor de peso de salida que lo normaliza por el peso total de salida de v. Estas fracciones determinan cuánto del rango de v se distribuye a u a través de esta arista específica.

Fórmula
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

Aplique la fórmula de PageRank Ponderado iterativamente: el rango de cada nodo es igual a un término base de teletransportación (1 menos el factor de amortiguación d, típicamente 0.85) más d veces la suma sobre todos los vecinos de entrada de su rango escalado por los dos factores de peso. Esto distribuye el rango proporcionalmente a la fuerza del enlace en lugar de uniformemente.

Fórmula
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

Repita la actualización de rango hasta que el cambio en la puntuación de cada nodo caiga por debajo de una pequeña tolerancia (comúnmente 1e-6). La convergencia está garantizada para grafos fuertemente conectados; para grafos con nodos colgantes o componentes aislados, aplique la corrección estándar de nodos colgantes antes de iterar.

5

Una vez que las puntuaciones han convergido, ordene todos los nodos por su puntuación de PageRank Ponderado en orden descendente. Estos rangos reflejan la importancia estructural global de cada nodo, considerando tanto la topología de la red como la fuerza de los enlaces.

Errores comunes

  • Usar pesos de arista brutos y no normalizados sin verificar su escala —mezclar recuentos en las decenas con valores en los millones distorsiona la propagación del rango.
  • Olvidar manejar los nodos colgantes (nodos sin aristas salientes), lo que puede drenar el rango de toda la red si no se corrige.
  • Asumir que el factor de amortiguación predeterminado de 0.85 es universalmente apropiado; en redes de citas o biológicas, un valor diferente puede reflejar mejor el dominio.
  • Interpretar las puntuaciones de PageRank Ponderado como probabilidades absolutas en lugar de clasificaciones relativas —solo su orden es estable en diferentes ejecuciones.
  • Comparar las puntuaciones de PageRank Ponderado entre redes de diferentes tamaños sin normalización.

Preguntas frecuentes

¿En qué se diferencia el PageRank Ponderado del PageRank estándar?

El PageRank estándar distribuye el rango de un nodo por igual a todos sus vecinos salientes, independientemente de la fuerza del enlace. El PageRank Ponderado escala esta distribución por el peso relativo de entrada y salida de cada enlace, de modo que las conexiones más fuertes transmiten proporcionalmente más rango.

¿Qué factor de amortiguación debo usar?

El valor convencional es 0.85, derivado de suposiciones de grafos web sobre la navegación aleatoria. Para redes sociales, biológicas o de citas, se exploran valores entre 0.5 y 0.9 en la literatura. Se recomienda un análisis de sensibilidad sobre un rango de valores de amortiguación.

¿Se puede aplicar el PageRank Ponderado a redes no dirigidas?

Sí, representando cada arista no dirigida como un par de aristas dirigidas con el mismo peso. El algoritmo produce entonces factores de peso de entrada y salida simétricos, lo que se simplifica a una fórmula que aún respeta la fuerza del enlace.

¿Cómo manejo los enlaces con peso cero?

Los enlaces con peso cero no contribuyen en nada a la propagación del rango, por lo que pueden eliminarse antes del análisis. Si los pesos cero son estructuralmente significativos (ausencia frente a datos faltantes), documente la distinción claramente antes de eliminarlos.

¿Es el PageRank Ponderado mejor que la centralidad de grado ponderado?

Depende de la pregunta de investigación. La centralidad de grado ponderado captura solo las conexiones directas, mientras que el PageRank Ponderado captura el prestigio global propagado a través de toda la red. Use el grado ponderado para la influencia local y el PageRank Ponderado para la importancia a nivel de red.

Métodos relacionados

Fuentes

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    Abrir referencia DOI
    Copiado.
  2. PageRank. Wikipedia.

    Abrir referencia de la publicación
    Copiado.