🔬 condensed matter

The distribution of eccentricities in random regular graphs

Este artículo deriva una expresión analítica de forma cerrada para la distribución completa de las excentricidades en grafos regulares aleatorios, revelando variaciones no triviales en las excentricidades de los nodos a pesar de los grados uniformes y proporcionando fórmulas precisas para la media, la moda y la varianza que sirven como referentes para analizar redes grandes y dispersas.

Autores originales: Dor Lev-Ari, Ofer Biham, Eytan Katzav

Publicado 2026-07-17

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Dor Lev-Ari, Ofer Biham, Eytan Katzav

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina una ciudad vasta e invisible donde cada persona es una casa, y cada amistad es un camino que las conecta. En el mundo de la ciencia, esto se llama un "red" o "red de contactos". Algunas redes son desordenadas, como un pueblo caótico donde algunas personas tienen un millón de amigos y otras no tienen ninguno. Pero existe una versión especial y perfectamente organizada de esta ciudad llamada "Grafo Regular Aleatorio". En esta ciudad, cada una de las casas tiene exactamente el mismo número de caminos que salen de ella; por ejemplo, tres o cinco. Es un mundo de perfecta igualdad, donde nadie está más conectado que los demás.

Los científicos saben desde hace tiempo que en estas ciudades la distancia promedio entre dos casas es sorprendentemente corta. Este es el efecto de "mundo pequeño": incluso en una ciudad enorme, generalmente puedes ir desde la puerta de tu casa hasta la de un extraño al otro lado de la ciudad en solo unos pocos pasos. Pero hay un truco. Aunque el viaje promedio es corto, el viaje más largo es lo que más importa. Si estás enviando un mensaje, un virus o un rumor, no importa qué tan rápido lo reciba la persona promedio; lo que importa es cuánto tarda en llegar a la última casa, la más aislada. Esta distancia máxima se llama "excentricidad". La gran pregunta es: si cada casa tiene exactamente el mismo número de caminos, ¿están todas a la misma distancia del borde del mundo, o la forma de la ciudad crea algunas casas que son naturalmente más "periféricas" que otras?

Un equipo de físicos de la Universidad Hebrea de Jerusalén decidió mapear este paisaje oculto. No se limitaron a suponer; construyeron un modelo matemático para describir la distribución completa de estas distancias. Descubrieron que, incluso en una ciudad donde todos están conectados por igual, la "distancia al borde" no es la misma para todos. En cambio, sigue un patrón muy específico y predecible que se asemeja a una escalera.

He aquí lo que descubrieron. Primero, derivaron una fórmula precisa que predice la probabilidad de que una casa tenga una determinada excentricidad. Piénsalo como un pronóstico del tiempo, pero en lugar de lluvia, predice qué tan lejos está una casa de los límites de la ciudad. Descubrieron que esta distribución sigue una forma conocida como la distribución de Gumbel (un nombre elegante para un tipo específico de curva de campana que trata con extremos). La fórmula que crearon utiliza tres ingredientes principales: el tamaño de la ciudad ( $N$ ), el número de caminos por casa ( $c$ ) y algunas constantes matemáticas.

La parte más fascinante de su descubrimiento es cómo se comporta la distancia "típica" a medida que la ciudad crece. Si graficas la distancia más común contra el tamaño de la ciudad, no aumenta suavemente como una rampa. En cambio, parece una escalera. Por un tiempo, la distancia más común se mantiene en, digamos, 5 pasos. Luego, cuando la ciudad crece solo un poco más, de repente salta a 6 pasos, se queda allí por un tiempo y luego salta a 7. Los autores llaman a este escalón de la escalera la "moda" de la distribución. Demostraron que este escalón de la escalera es siempre el número entero más cercano a la distancia "promedio". Así que, si las matemáticas dicen que la distancia promedio es 5.8, la distancia más común para casi todos es 6.

También observaron cuánto varían estas distancias. En un mundo continuo y suave, uno esperaría que la variación fuera mínima. Pero debido a que las distancias en una ciudad se cuentan en pasos enteros (no puedes caminar 5.5 pasos), la variación oscila hacia arriba y hacia abajo como un latido a medida que la ciudad crece. Cuando la ciudad está a punto de saltar de una distancia de 5 a 6, la variación alcanza un pico porque algunas casas están atrapadas en 5 mientras que otras ya han alcanzado 6. En estos "puntos de inflexión", la variación es de aproximadamente 0.25, que es el máximo posible para un escenario de lanzamiento de moneda donde la mitad de las casas están en una distancia y la otra mitad en la siguiente.

Los investigadores probaron sus matemáticas ejecutando simulaciones por computadora de estas ciudades, creando miles de redes con diferentes tamaños. Encontraron que sus fórmulas coincidían casi perfectamente con los resultados de la computadora, especialmente a medida que las ciudades se hacían más grandes. Por ejemplo, en una ciudad donde cada casa tiene 5 caminos ( $c=5$ ), cuando la ciudad tiene unas 160 casas, casi todos están a 5 pasos del borde. Pero una vez que la ciudad crece a 440 casas, casi todos están repentinamente a 6 pasos de distancia.

¿Por qué es esto importante? Imagina que eres un repartidor, un emisor de transmisiones o un virus. No te importa el tiempo de entrega promedio; te importa el peor de los escenarios. ¿Cuánto tiempo tarda un mensaje en llegar a la casa absolutamente más lejana? Este artículo nos brinda una herramienta precisa para calcular ese retraso del peor escenario para cualquier red donde todos tengan el mismo número de conexiones. Resulta que, incluso en una red perfectamente justa, la geometría del espacio crea un "borde" natural, y la distancia a ese borde crece de una manera específica, paso a paso. Los autores sugieren que sus fórmulas pueden servir como un punto de referencia para verificar qué tan bien funcionan los algoritmos informáticos cuando intentan calcular estas distancias en redes enormes y dispersas. En resumen, han demostrado que, incluso en un mundo de perfecta igualdad, el mapa hacia el borde tiene un ritmo, y ese ritmo es una escalera.

Resumen Técnico: La Distribución de Excentricidades en Grafos Regulares Aleatorios

Planteamiento del Problema
Los Grafos Regulares Aleatorios (RRG, por sus siglas en inglés), donde cada nodo posee un grado idéntico $c$ , son un conjunto fundamental en la teoría de redes. Mientras que la estructura local de estos grafos está definida por la distribución uniforme de grados, su estructura a gran escala está caracterizada por la distribución de las longitudes de los caminos más cortos (DSPL) y las excentricidades de los nodos. La excentricidad de un nodo se define como la distancia máxima desde dicho nodo hacia cualquier otro nodo en la red. Aunque los grados de todos los nodos son idénticos en un RRG, las excentricidades exhiben variaciones no triviales. El artículo aborda la falta de una expresión analítica de forma cerrada para la distribución completa de estas excentricidades (DoE), señalando que la literatura existente a menudo se centra en escalas de longitud características únicas (como la media o el diámetro) en lugar de la distribución estadística completa. Comprender la DoE es crítico para aplicaciones prácticas como la difusión (broadcasting) y la diseminación global, donde el rendimiento de la red está dictado por los tiempos de retraso en el peor de los casos (excentricidad máxima).

Metodología
Los autores emplean métodos de la teoría de valores extremos para derivar la DoE para RRGs que constan de $N$ nodos de grado $c \ge 3$ . La derivación procede a través de los siguientes pasos:

Fundamentación en la DSPL: El estudio utiliza la expresión analítica de forma cerrada conocida para la cola de la DSPL, $P(L > \ell)$ , la cual sigue una distribución de Gompertz discreta.
Aplicación de la Teoría de Valores Extremos: Tratando la excentricidad de un nodo como el máximo de $N-1$ distancias a otros nodos, los autores modelan la DoE. Asumiendo correlaciones débiles entre las distancias en redes suficientemente grandes, la distribución acumulada del máximo se aproxima utilizando la distribución de la cola de la DSPL subyacente.
Derivación Analítica: Al sustituir la cola de la DSPL en el marco de valores extremos, los autores derivan una expresión de forma cerrada para la distribución de la cola de las excentricidades, $P(E > \ell)$ .
Momentos Estadísticos: Utilizando la fórmula de la suma de la cola y la técnica de sumación de Euler-Maclaurin, los autores derivan expresiones de forma cerrada para la excentricidad media $\langle E \rangle$ , la moda $E_{\text{mode}}$ y la varianza $\text{Var}(E)$ .
Validación: Los resultados analíticos se validan frente a simulaciones computacionales de RRGs generados mediante un procedimiento de emparejamiento de estobas (stub-matching) seguido de un proceso de intercambio de aristas para eliminar bucles de autodirección y múltiples aristas. Las simulaciones se promediaron sobre 1,000 instancias de red para diversos tamaños $N$ y grados $c$ .

Contribuciones Clave y Resultados

Distribución de Forma Cerrada: La contribución principal es la derivación de la distribución de la cola de las excentricidades:
$P(E > \ell) \simeq 1 - \exp\left[ -\exp\left( -\frac{e^{b\ell} - \mu}{\beta} \right) \right]$
donde $b = \ln(c-1)$ es el parámetro de forma, $\beta = \frac{c-2}{c}N$ es el parámetro de escala, y $\mu = \frac{c-2}{c}N \ln N$ es el parámetro de localización. Esta distribución se asemeja a una distribución de Gumbel, pero presenta un término exponencial en el argumento en lugar de uno lineal.
Excentricidad Media: Se deriva una expresión de forma cerrada para la excentricidad media:
$\langle E \rangle \simeq \frac{\ln N}{\ln(c-1)} + \frac{\ln \ln N}{\ln(c-1)} - \frac{\ln c - \ln(c-2)}{\ln(c-1)} + \frac{1}{2} + O\left(\frac{1}{\ln N}\right)$
Los autores señalan que, mientras los resultados de las simulaciones se fijan en valores enteros, la expresión analítica proporciona un contorno suavizado que elucida el comportamiento de escala.
Moda y Perfil de Escalera: Se encuentra que la moda de la DoE, $E_{\text{mode}}$ , exhibe un perfil de escalera en función del tamaño de la red $N$ . Los autores demuestran que la moda es simplemente el entero más cercano a la media: $E_{\text{mode}} = \text{Round}(\langle E \rangle)$ . Los puntos de transición entre los valores enteros de la moda se determinan utilizando la función $W$ de Lambert.
Varianza y Oscilaciones: La varianza $\text{Var}(E)$ es calculada y se muestra que exhibe oscilaciones como función de $N$ . Estas oscilaciones surgen de la naturaleza discreta de la excentricidad. La varianza alcanza picos cerca de los bordes de los escalones donde la moda cambia de $\ell$ a $\ell+1$ , alcanzando un valor máximo de aproximadamente $1/4$ cuando la distribución es efectivamente binaria ( $P(E=\ell) \approx P(E=\ell+1) \approx 1/2$ ).
Efectos de Tamaño Finito: Los resultados analíticos muestran una excelente concordancia con las simulaciones para $N$ grandes. Las discrepancias observadas en redes más pequeñas se atribuyen a efectos de tamaño finito, particularmente cerca de los puntos de transición de la distribución de la cola.

Significancia
El artículo afirma que proporcionar la distribución completa de las excentricidades, en lugar de solo una escala de longitud característica, ofrece una visión detallada de la estructura a gran escala de los RRGs. Las expresiones analíticas derivadas sirven como referentes para los enfoques algorítmicos de cálculo de excentricidades en redes dispersas grandes. Los resultados resaltan que, incluso en redes con grados uniformes, las excentricidades varían significativamente, y estas variaciones son capturadas por la distribución derivada. El trabajo confirma que la DoE es una distribución estrecha, lo que implica que la diferencia entre el diámetro de la red (excentricidad máxima) y el radio (excentricidad mínima) es de orden 1. Los autores concluyen que estos hallazgos son relevantes para aplicaciones prácticas donde el rendimiento de la red está determinado por los tiempos de retraso más largos, como en los protocolos de difusión y diseminación global.

Más como este