Optimización de rankings en estructuras jerárquicas mediante el modelo gravitacional.
Autores
- Alberto García Robledo, SECIHTI – CentroGeo
- Mahboobeh Zangiabady, University of Twente
- Jotte Sonneveld, Eye Security
Resumen
Este artículo presenta un enfoque innovador para mejorar la identificación de nodos influyentes en redes dirigidas acíclicas (DAGs), mediante la adaptación del modelo gravitacional de centralidad. Se propone un algoritmo eficiente en tiempo casi lineal para su cálculo y se evalúa su capacidad para mejorar tanto la precisión como la resolución de los rankings, especialmente en redes con estructuras jerárquicas o temporales. El estudio, realizado en el Observatorio Metropolitano de CentroGeo en colaboración internacional, abre nuevas posibilidades para aplicar modelos de propagación e influencia en estructuras acíclicas presentes en sistemas urbanos y metropolitanos.
Introducción
En el análisis de redes sociales y urbanas, los grafos dirigidos acíclicos (DAGs) representan una estructura fundamental para modelar relaciones que tienen un orden temporal o jerárquico. Este tipo de grafos aparece de forma natural en contextos como redes de citas científicas, sistemas organizativos, jerarquías de decisiones y flujos de información.
A diferencia de los grafos cíclicos o no dirigidos, los DAGs presentan desafíos específicos en la aplicación de métricas de centralidad. Muchas de las técnicas clásicas —como PageRank o centralidad de intermediación— fueron originalmente diseñadas para redes donde la retroalimentación es posible. En los DAGs, sin ciclos, se requiere adaptar estos enfoques para capturar adecuadamente la influencia de un nodo dentro de la estructura jerárquica.
En este contexto, el modelo gravitacional de centralidad, inspirado en la Ley de Gravitación Universal de Newton, ofrece una alternativa prometedora. Este modelo considera tanto la “masa” de los nodos —definida por una métrica de centralidad base como el k-shell— como la distancia geodésica, ponderando así la influencia en función de la cercanía estructural.
Nuestro estudio —realizado en el marco del Observatorio Metropolitano de CentroGeo en colaboración con la University of Twente y Eye Security— representa el primer análisis exhaustivo del modelo gravitacional aplicado específicamente a DAGs. Se propone además un algoritmo eficiente, se evalúa el desempeño del modelo con distintas métricas de centralidad y se analiza su comportamiento en más de 3,000 DAGs sintéticos y empíricos.
Un estudio realizado desde el Observatorio Metropolitano de CentroGeo
El trabajo presentado en este artículo fue desarrollado en el Observatorio Metropolitano de CentroGeo, en colaboración con el grupo SECIHTI, la University of Twente (Países Bajos) y la empresa Eye Security (Países Bajos). El objetivo principal fue adaptar y evaluar el modelo gravitacional de centralidad dentro del contexto de grafos dirigidos acíclicos, una estructura clave en redes urbanas jerárquicas y de propagación.
En el artículo original publicado en la revista Social Network Analysis and Mining (2025), disponible en este enlace, proponemos un algoritmo eficiente en tiempo casi lineal, optimizado para DAGs, que permite calcular el índice gravitacional sin necesidad de calcular todas las distancias entre pares de nodos. Esto representa un avance significativo frente a algoritmos previos con complejidad cuadrática.
Además del algoritmo, se estudiaron cinco índices de centralidad clásicos como masa gravitacional: grado de salida, centralidad de intermediación, centralidad de cercanía, k-shell y centralidad de alcance. Al combinarlos con el modelo gravitacional se generaron diez variantes distintas de centralidad, evaluadas sobre más de 2,000 DAGs sintéticos y 1,000 DAGs empíricos.
Resultados
Se evaluaron cinco índices de centralidad combinados con el modelo gravitacional (out-degree, betweenness, closeness, reach y k-shell), generando un total de diez variantes.
Los resultados principales fueron:
- Mejora en precisión de rankings: la correlación de los rankings generados con el modelo gravitacional frente a los resultados de simulaciones de propagación (modelo SIR) aumentó hasta un 105% en DAGs tipo Layer-by-layer, especialmente al combinar gravedad con k-shell o closeness.
- Aumento en la resolución de rankings (monotonicidad): se observó un incremento de hasta 194 veces en la capacidad de distinguir nodos usando gravedad sobre k-shell en DAGs Recursivos, y mejoras también sustanciales en DAGs tipo Erdős-Rényi.
- Limitaciones en DAGs altamente centralizados: en DAGs como Poset o en redes de citación poco profundas, las mejoras fueron marginales o incluso nulas, especialmente con índices como reach o out-degree.
- El índice k-shell fue el más potenciado por la gravedad: tanto en precisión como en monotonicidad, fue sistemáticamente el índice más beneficiado por la incorporación del modelo gravitacional.
Estos hallazgos respaldan el uso del modelo gravitacional en DAGs estructuralmente diversos y destacan su valor para identificar nodos influyentes cuando se combinan con métricas adecuadas y redes con suficiente profundidad jerárquica.
Implicaciones para el análisis metropolitano
En los sistemas urbanos de transporte, especialmente en contextos metropolitanos complejos, los flujos de vehículos o personas suelen organizarse siguiendo trayectorias dirigidas que rara vez forman ciclos completos. Estas trayectorias, como los trayectos de entrada y salida a través de nodos viales, intercambiadores o estaciones intermodales, pueden representarse eficazmente como grafos dirigidos acíclicos (DAGs). En este tipo de representaciones, cada nodo puede corresponder a un punto de control, una intersección o una etapa en la cadena de movilidad.
Contar con herramientas que permitan identificar los nodos más influyentes dentro de estas estructuras jerárquicas puede ser clave para:
- Detectar puntos críticos que concentran la propagación de congestión o demoras.
- Optimizar la jerarquía semafórica y los patrones de sincronización vial.
- Evaluar el impacto estructural de modificaciones en rutas troncales o proyectos de infraestructura.
Los resultados del estudio, al haber considerado una amplia variedad de modelos generativos de DAGs —más allá de los típicamente usados en redes sociales—, son relevantes para otros dominios como los DAGs de trayectorias urbanas. Esto abre posibilidades de aplicar el modelo gravitacional para detectar puntos de control, identificar trayectos estructuralmente influyentes y optimizar el flujo en redes de movilidad metropolitana.
Conclusiones
El estudio desarrollado en el Observatorio Metropolitano de CentroGeo en colaboración con instituciones internacionales demuestra que el modelo gravitacional, originalmente concebido para redes cíclicas, puede adaptarse con éxito a grafos dirigidos acíclicos (DAGs). Esta adaptación no solo es factible desde el punto de vista computacional —gracias a un algoritmo diseñado para ejecutarse en tiempo casi lineal en DAGs grandes—, sino que también aporta beneficios concretos en la precisión y resolución de los rankings de nodos.
Uno de los hallazgos más relevantes es que el modelo gravitacional incrementa significativamente la capacidad discriminativa del índice k-shell, especialmente en DAGs con estructura jerárquica profunda y descentralizada. Estos hallazgos son relevantes para sistemas urbanos donde la jerarquía del flujo —como en la movilidad o el tránsito metropolitano— tiene un papel fundamental.
Asimismo, se evidenció que los beneficios del modelo gravitacional dependen de la combinación adecuada entre estructura de red y métrica base utilizada. Mientras que algunos índices como la centralidad de cercanía o la de alcance mostraron mejoras más discretas, el k-shell sobresalió como el más potenciado por la propagación gravitacional. Este conocimiento puede guiar futuras aplicaciones del modelo en dominios urbanos.
Referencia bibliográfica
García-Robledo, A., Zangiabady, M., & Sonneveld, J. (2025). Exploring the gravitational model for ranking influential nodes in directed acyclic networks. Social Network Analysis and Mining, 15(83). https://doi.org/10.1007/s13278-025-01500-4