Todo son grafos y poesía

Cuando estaba en el colegio, hubo un profesor que me dijo algo que, por algún motivo, se me quedó grabado en la memoria: "todo son matrices y poesía". Aunque su afirmación tenía un tono jocoso, intuía que escondía una verdad profunda. Hoy me voy a apropiar de ella diciendo que "todo son grafos y poesía", y con ello explorar la fascinante omnipresencia en multitud de aplicaciones.

¿Qué es un grafo?

Es muy sencillo. Un grafo se compone fundamentalmente de dos elementos: nodos y vértices (o aristas). Los nodos representan estados o entidades, mientras que los vértices conectan (o no) dichos nodos. Los grafos pueden estar dirigidos o no dirigidos, que se indica entonces con una flecha que comienza en un nodo y acaba en otro.

Resulta sorprendente que este concepto tan poderoso permanezca relativamente oculto en muchos planes de estudio de carreras técnicas. Personalmente, pensar un problema en términos de grafos se ha convertido en una de mis primeras aproximaciones ante cualquier desafío complejo. Es una herramienta visual y conceptual increíblemente valiosa que nos permite modelar situaciones de contextos variopintos.

Los grafos están por todas partes

A continuación mencionaré tan solo algunos ejemplos de ámbitos donde podemos analizar sistemas complejos en términos de grafos:

1. Redes sociales

Quizás el ejemplo más intuitivo actualmente: en una red social, las personas son los nodos y las conexiones (amistad, seguimiento, interacción) son los vértices. El análisis de estos grafos permite desde recomendar nuevas amistades hasta detectar comunidades o identificar influencers.

Este grafo representa una pequeña red social donde cada nodo es una persona y las aristas (flechas) indican "quién sigue a quién". Las relaciones están dirigidas, lo que significa que si hay una flecha de Ana a Berto, Ana sigue a Berto, pero no necesariamente a la inversa.

2. Redes logísticas

Imagina una red logística con varias ciudades. Cada ciudad es un nodo, y las carreteras que las conectan son los vértices. Esta representación visual inmediatamente nos permite entender la estructura de la red, identificar rutas óptimas o detectar puntos críticos cuya eliminación podría desconectar partes de la red.

En este ejemplo encontramos una red logística donde cada nodo representa una ciudad española importante y cada arista representa una conexión directa entre ciudades. El grafo no está dirigido porque asumimos que las conexiones permiten el tráfico en ambas direcciones.

Esta representación nos permite identificar rápidamente aspectos importantes de la red como:

• Rutas directas entre ciudades

• Puntos críticos (si Madrid quedara aislada, la red se fragmentaría significativamente)

• Ciudades mejor conectadas (Madrid tiene cuatro conexiones, convirtiéndola en el principal hub logístico del país)

3. Mercados financieros

En el ámbito financiero también es posible sacar mucho partido de los grafos. Un grafo de mercado puede formarse considerando cada activo financiero como un nodo. Las correlaciones entre los rendimientos de estos activos serán la base para construir los vértices del grafo.

De manera más rigurosa, podemos formular este grafo basándonos en el coeficiente de correlación de Pearson (r) entre los rendimientos o rendimientos logarítmicos de pares de acciones. Estas correlaciones pueden tomar valores entre -1 y 1, indicando correlaciones negativas perfectas o positivas perfectas, respectivamente.

Para construir un grafo de conexiones muy sencillo, podemos aplicar un método de umbral de correlación (θ), donde existirá una arista entre los nodos i y j si su correlación correspondiente (r_ij) es mayor o igual a este umbral (r_ij ≥ θ).

En este ejemplo, cada nodo representa una acción importante y cada arista representa una correlación significativa entre los movimientos de precios. Se incluye dos sectores claramente diferenciados: el tecnológico (Apple, Microsoft, Amazon, Google, Meta) y el financiero (JP Morgan, Bank of America, Goldman Sachs, Wells Fargo, Morgan Stanley).

Un grafo nos permite identificar no solo grupos de acciones que tienden a moverse juntas dentro de un mismo sector, sino también las limitadas conexiones entre sectores diferentes. Observamos que Apple tiene correlación con JP Morgan y Microsoft con Goldman Sachs, pero en general hay pocas conexiones intersectoriales, lo que sugiere buenas oportunidades de diversificación al invertir en ambos sectores.

4. Análisis lingüístico

Ahora exploremos un último ejemplo menos evidente pero igualmente fascinante. En el campo del análisis lingüístico, podemos representar las palabras como nodos de un grafo. Los vértices entre estas palabras pueden indicar distintos tipos de conexiones, como por ejemplo:

• Que dos palabras aparecen juntas frecuentemente en un texto (coocurrencia)

• Que una palabra suele seguir a otra en un texto (secuencia)

Este enfoque nos permite hacer cosas muy interesantes. Por ejemplo, podemos usar cadenas de Markov para generar texto nuevo siguiendo los patrones de probabilidad de las conexiones entre palabras. También podemos analizar la estructura estilística característica de un autor determinado.

De hecho, el grafo resultante funciona como una especie de "huella digital" lingüística, revelando patrones únicos en el vocabulario y la construcción de frases que son característicos de cada escritor. Esta técnica nos permite incluso identificar la autoría de textos anónimos comparando sus grafos lingüísticos con los de autores conocidos.

¿Por qué hay grafos por todas partes?

Aquí está el insight: ¡los grafos codifican relaciones! Y las relaciones son la esencia misma de nuestro mundo. Nada existe de forma aislada; todo es lo que es sólo en la medida en que se relaciona o no con todo lo demás. El concepto de relación se encuentra en la base irreductible de la existencia misma.

Las partículas que forman nuestro universo interaccionan entre sí siguiendo los dictados de las leyes de la física. Las partículas elementales del universo se organizan para dar lugar a átomos, moléculas, células, tejidos orgánicos, neuronas, y finalmente un cerebro y un cuerpo que usamos para entender ese mismo orden del que provenimos. Si los objetos no se relacionasen, el universo sería un lugar estrictamente aleatorio, y nada interesante ocurriría en él.

Los grafos no aparecen en diversos contextos por accidente. Aparecen porque son manifestaciones visuales de nuestro conocimiento sobre las relaciones en un sistema. Y seguirán apareciendo en absolutamente todas partes en tanto seamos capaces de concretar ese tipo de conocimiento. Son estructuras fundamentales porque representan algo igualmente fundamental: ¡la interconexión de las cosas!

Grafos y matrices: dos caras de la misma moneda

Y aquí llegamos a una revelación fascinante: un grafo puede representarse perfectamente mediante una matriz (llamada matriz de adyacencia), y viceversa. Cada fila y columna de la matriz corresponde a un nodo, y los valores indican si existe conexión entre ellos y, de ser así, su peso o intensidad.

Así que mi profesor tenía razón después de todo: todo son matrices y poesía. O grafos y poesía, que viene a ser lo mismo. Las estructuras matemáticas que capturan relaciones (sean matrices o grafos) y la capacidad humana de encontrar belleza y significado en esas conexiones.

¿Y qué tiene que ver todo esto con algoritmos de inspiración cuántica?

Resulta que existen varios problemas definidos sobre grafos que son computacionalmente complejos. Detectar estructuras específicas como cliques (subconjuntos de nodos donde todos están conectados entre sí) o conjuntos independientes (conjuntos de nodos donde ninguno está conectado con otro del mismo conjunto) son problemas clasificados como NP-Hard.

Estos problemas combinatorios representan un desafío formidable para los algoritmos convencionales, que frecuentemente se ven obligados a recurrir a aproximaciones o heurísticas cuando el tamaño del grafo crece.

Aquí es donde entran en escena los algoritmos de inspiración cuántica, como los que desarrollamos en Inspiration-Q, diseñados específicamente para abordar estos problemas combinatorios complejos con mayor eficiencia. Estos algoritmos pueden explorar múltiples soluciones simultáneamente y converger hacia soluciones óptimas o casi óptimas mucho más rápidamente. Lo mejor es que todo este conocimiento lo hemos paquetizado en una plataforma API que llamamos iQ-Xtreme, con la que uno puede utilizarlos sin tener que preocuparse más que por la definición de tu grafo como una matriz.

¿Quieres saber más?

¿Quieres profundizar aún más sobre el significado de las relaciones, matrices y grafos? Te recomiendo consultar los capítulos 1 y 7 de "Todo lo que puedo imaginar: El algoritmo del entendimiento".

¿Quieres saber más sobre optimización de grafos con algoritmos de inspiración cuántica? Echa un vistazo a nuestra web y contáctanos