De Big Data a Ramanujan: grafos expander

Un recorrido visual y conceptual guiado por la imagen de un expander 3‑regular

Nodo inicial: ¿Por qué mirar grafos en Big Data?

En las clases que doy sobre Big Data y Grafos, uno de los temas tratados es el de los grafos regulares. Estas redes, donde cada nodo tiene exactamente el mismo número de conexiones, parecen simples a primera vista, pero encierran comportamientos extraordinarios. Lo que a menudo sorprende es que estructuras con tan poca densidad de enlaces pueden ser increíblemente eficientes para transmitir información, distribuir tareas o resistir fallos. A partir de esa idea, construí esta nota como un recorrido guiado, como si fuera un grafo acíclico dirigido: sin ciclos, con una dirección clara, donde cada concepto lleva naturalmente al siguiente aplicado en este caso a un grafo regular que no es un DAG, sino un grafo no dirigido y cíclico. La idea de “DAG” la aplico como metáfora de progresión, no al objeto representado, porque esta nota se centra en una imagen concreta que ilustra muchas de las ideas exploradas teóricamente.

DAG y grafos

Mostrar animación original

Nodo central: la imagen que guía todo

Topología y espectro de un expander 3‑regular

Mostrar animación original

La imagen está dividida en dos partes. A la izquierda, un grafo 3‑regular con 50 nodos, cada uno con tres conexiones coloreadas según su centralidad de vector propio. Esa métrica espectral revela qué nodos influyen más en el flujo de información. Aunque no hay hubs, el grafo se mantiene cohesionado.

Más allá de su funcionalidad, la visualización tiene un gran valor estético: líneas curvas, colores graduales y simetría informal recuerdan obras de arte geométrico. En ciencia de datos, una buena visualización revela patrones invisibles: este grafo no solo funciona, sino que también se deja mirar.

A la derecha se representa el espectro de la matriz de adyacencia. La curva semicircular es una comparación visual. Para grado fijo, como $d=3$, la densidad límite de grafos regulares aleatorios es Kesten–McKay; la ley semicircular de Wigner aparece al crecer el grado, con normalización adecuada. Una muestra de 50 nodos no demuestra una ley límite.

Nodo intermedio: la paradoja de los expanders

Un expander combina baja conectividad local con alta conectividad global. Permite distribuir información robusta y eficientemente sin enlaces redundantes. No hay rutas únicas ni dependencias críticas: cada nodo conecta rápidamente con el resto. Esa paradoja de “poca densidad, gran cohesión” lo hace valioso en teoría de la computación, diseño de redes, codificación y sistemas distribuidos.

Nodo de análisis: los autovalores como herramienta

La matriz de adyacencia sin normalizar tiene autovalor principal $d$; la brecha espectral es $d-\lambda_2$. La cota asintótica de Alon–Boppana contiene el factor 2: para grado 3, $2\sqrt{2}\approx2{,}83$. Un grafo Ramanujan exige $|\lambda|\leq2\sqrt{d-1}$ para todos los autovalores no triviales; se excluyen $d$ y, si corresponde, $-d$. La imagen por sí sola no verifica esta condición.

Nodo histórico: Ramanujan, Wigner y una apuesta famosa

Los Ramanujan graphs conectan teoría de números y expansión. La apuesta de Sarnak y Alon inspiró una pregunta sobre su frecuencia. Huang, McKenzie y Yau demostraron universalidad de los autovalores extremos: aproximadamente el 69 % de los grafos regulares aleatorios de grado fijo son Ramanujan en el límite de muchos vértices. No es una garantía para cada grafo de 50 nodos.

Mostrar animación original

La gráfica radial presenta el histograma y una curva de comparación. Su valor visual conecta topología y espectro; para interpretar cuantitativamente un grafo de grado fijo, corresponde usar Kesten–McKay.

Nodo aplicado: por qué esto importa en Big Data

En la práctica, los expanders optimizan sistemas distribuidos, redes resistentes y algoritmos más rápidos. En entornos de Big Data, donde millones de operaciones coordinan sin saturarse, minimizan enlaces y maximizan eficiencia. También impulsan arquitecturas neuronales, protocolos criptográficos y diseños de supercomputadoras.

Cómo se expande el flujo en una red regular

Mostrar animación original

La animación muestra cómo, en dos saltos, el flujo parte del nodo 0 hacia sus vecinos de primer nivel (42, 38, 33) y luego al segundo (13, 15, 19, 20, 26, 39). Con solo tres enlaces por nodo, el “río de datos” llega rápidamente a esos nodos del segundo nivel.

Glosario técnico

• Grafo regular: todos los nodos tienen el mismo número de conexiones (grado).
• Expander: grafo con baja conectividad local pero alta conectividad global.
• Autovalores: números de la matriz de adyacencia que revelan propiedades estructurales.
• λ₂: segundo mayor autovalor, indicador clave de expansión.
• Ramanujan graph: grafo $d$-regular cuyos autovalores no triviales satisfacen $|\lambda|\leq2\sqrt{d-1}$.
• Ley semicircular de Wigner: distribución estadística de autovalores de matrices aleatorias.

Bibliografía y base conceptual

• Huang, McKenzie y Yau (2025): Ramanujan Property and Edge Universality of Random Regular Graphs.

• Bauerschmidt, Huang y Yau: Local Kesten–McKay law for random regular graphs.

• Quanta Magazine (2025): “New Proof Settles Decades-Old Bet About Connected Networks”

• Noga Alon & Peter Sarnak, teoría de grafos expandidos

• Horng‑Tzer Yau, Jiaoyang Huang y Theo McKenzie, demostración de la universalidad en grafos regulares

• Big Data & Graph Theory Lectures, curso 2024

Epílogo

Como en un grafo acíclico dirigido, este recorrido tuvo un camino claro y sin retrocesos. Empezamos con una imagen sencilla, profundizamos en teoría, atravesamos una historia matemática y llegamos a conclusiones prácticas. Hoy, esos nodos y enlaces mínimos son una puerta a uno de los conceptos más potentes y elegantes de la teoría de grafos: eficiencia y belleza de la mano.