Grafos: Las Redes que mueven el mundo

Las calzadas romanas, la red eléctrica y, recientemente, Internet. Todas las redes que el ser humano ha diseñado para su comunicación y progreso tienen algo en común: se pueden representar mediante grafos que nos ayudan a modelar y comprender mejor cómo funcionan.

Para entender qué es un grafo, viajemos al año 1736, cuando Leonard Euler publica la solución del “problema de los puentes de Könisberg”.  En él se planteaba cómo cruzar los siete viaductos de la ciudad que vadeaban el río Pregolya, pasando exclusivamente una vez por cada uno. Euler se ayuda de un grafo donde las distintas áreas de la ciudad son los “nodos” o “vértices”, y los puentes que los unen son “aristas” o “arcos”. Recomiendo prestar un minuto de atención a la figura adjunta, donde se puede ver el problema original y su grafo correspondiente. Es más, os animo a coger lápiz y papel, y buscar la solución del dilema.

Nótese que Euler marcó los nodos en Mayúsculas y los arcos en minúsculas

Explosión combinatoria

Encontrar caminos en un grafo tan simple como este puede tomarnos unos minutos en papel y un instante en el ordenador. Podemos escribir todas las combinaciones posibles de arcos que parten de A, y luego ir eliminando los caminos imposibles. Así, descartamos el primero de todos, “a-b-c-d-e-f-g”, porque no se puede ir del arco f al g debido a que nos encontramos en la región B. Antes de que hagáis la lista advierto que hay 7! = 5040 combinaciones. Cuando el tiempo de resolución de un problema depende de un factor exponencial del número de elementos, se llama “np-completo” ( “np” viene de “no polinómico”).

La fuerza bruta del ordenador puede quedarse pequeña a poco que aumentemos el tamaño del grafo. Por suerte, algunos problemas de esta índole se pueden resolver usando métodos análogos que empleen tiempos polinómicos. Nadie ha podido demostrar o refutar que siempre exista esta correspondencia. Es más, se ha convertido en uno de los grandes problemas de las matemáticas, por el que el Clay Mathematics Institute ofrece un millón de dólares a quien consiga una demostración en algún sentido.

¿Qué ocurre en la práctica? Las empresas que necesitan de estas técnicas hacen de tripas corazón y se conforman con una solución que les sea factible, aunque sepan que no es la mejor. Para que se hagan una idea, el problema de Könisberg se simplifica si se permite pasar dos veces por un puente.

Topologías
Según se conecten los nodos tendremos distintas topologías. La más simple es una lista ordenada de objetos, donde un nodo sigue a otro. Si unimos el primero y último de ellos, tendremos un grafo cíclico. En algunos casos necesitamos evitar por todos los medios estos bucles. Cobran así importancia ciertos grafos con una característica muy especial: los árboles.

Como en la naturaleza, un árbol es un grafo que parte de un nodo padre (raíz), y desde éste un único arco (ramas) a cada uno de sus nodos hijos. Esta ley se puede aplicar de nuevo, formando un nuevo nivel de nodos. Un esquema, un análisis sintáctico, un reparto de tareas… hay miles de problemas que se pueden modelar con un árbol.

Podemos representar nuestro problema con un árbol donde las ramas son los puentes y los nodos representan el área donde nos encontramos al atravesarlo. En la figura se muestran dos niveles incompletos del mismo. Si conseguimos llegar al séptimo nivel, habremos encontrado la deseada respuesta.

Para mayor claridad, se han dejado sin desarrollar los nodos marcados con “...”

Mover, pensar, repartir

En la actualidad solo quedan cinco puentes en Könisberg. Pero, ¿Y si fueran levadizos? La configuración del grafo cambiaría dinámicamente. Apenas hemos comenzado a estudiarlos, y los modelos que se han propuesto no satisfacen plenamente las necesidades generadas en la vida real, sobre todo en su aplicación a la estructura de Internet y a la de las redes sociales. Con ello se pretende encontrar nodos aislados o que sean centro de atención, caminos redundantes... Más aún, según la teoría de la percolación estamos aprendiendo más sobre cómo se propagan las catástrofes naturales; algo muy importante para saber cómo detenerlas. Resulta paradójico, pero existe cierto orden en estas redes generadas de forma caótica.

¿Y si a estos nodos les damos capacidad de cómputo? Los investigadores en redes neuronales artificiales, partiendo de un modelo simplificado del comportamiento de estas células del cerebro, han conseguido resolver con solvencia problemas de aprendizaje de patrones, previsión, control, clasificación… y hasta soluciones a problemas np-completos.

Los métodos centralizados, pues, dejan de tener sentido con estos algoritmos distribuidos donde cada nodo realiza una parte de la tarea. De hecho, es así como se computa el camino para encontrar a otro ordenador en Internet, y cada vez más tareas complejas con sencillos ordenadores. De esta forma nació el más pionero de estos programas, el proyecto SETI@home; que pide a los usuarios de Internet el tiempo que está su ordenador inactivo para analizar muestras de señales de radio procedentes del espacio exterior en busca de patrones que den indicios de vida inteligente en su emisión. Aunque no se han encontrado las deseadas señales, el modelo es tan interesante que se ha copiado para otros proyectos científicos.

En casi tres siglos, el estudio de teoría de grafos se ha topado con la complejidad extrema, con problemas irresolubles, o cuya solución abarcan tiempos inaceptables. Hemos comenzado a comprender cómo se comportan estos mecanismos relacionales, y a sacar partido de ello. Las redes dinámicas y los procesos distribuidos son nuestro presente. Estamos continuamente tejiendo hilos que conforman nuestras relaciones profesionales y personales de las que tan solo estamos comenzando a comprender cómo son estas redes, y cómo mueven el mundo.

Nota: Para aquellos que aún no lo han averiguado: El problema de los puentes de Könisberg es irresoluble. No hay forma de pasar una sola vez por cada puente. Su demostración, llena de ingenio imposible de reproducir por las máquinas, puede leerse aquí.

Jorge J. Frías Perles

Facebooktwitterredditpinterestlinkedin

Etiquetas: , , , , ,

10 Comentarios en “Grafos: Las Redes que mueven el mundo”

  1. Avatar
    oscarhuertas diciembre 13, 2012 at 7:16 pm #

    Muy buena entrada Jorge, a pesar de lo complejo del tema lo has explicado muuuy sencillito y muy bien. Gracias.

    Oye una cosa, se puede estudiar la complejidad de estas redes con parámetros fractales? la complejidad de estas redes en sí tiene valor? supongo que en todo caso sería estudiable si tenemos en cuenta que todos los nodos tienen el mismo peso y los vectores que los unen la misma importancia.

    De nuevo felicidades por el post. muy chulo.

    • Avatar
      jorgejfrias diciembre 14, 2012 at 11:09 am #

      Veo Óscar que te gusta el "heavy metal" de las redes 🙂

      No he profundizado gran cosa en este tema, pero sí que se están trabajando cosas sobre el mismo. Ten en cuenta que la propia curva de Sierpinski puede ser modelada como un grafo que va cambiando con el tiempo según una serie de transformaciones conocidas.

      Aquí tienes un ejemplo:
      http://matematicas.uis.edu.co/~integracion/rint-html/volumen/vol19(1)2001/2MESAHeber-nuevo.pdf

      • Avatar
        oscarhuertas diciembre 15, 2012 at 7:16 pm #

        jaja, Efectivamente me refería a este heavy de las redes. Es un tema que me fascina pero no termino de encontrar una aplicación real. No estoy tan seguro de que el grado de complejidad de una red dada (construida por nosotros de forma artificial) pueda ser una dato relevante para estudiar sistemas. Muchas gracias por el enlace, esta muy bien el artículo.

  2. Avatar
    Aníbal Bueno diciembre 13, 2012 at 2:33 pm #

    Muy bueno Jorge, yo como Bioinformático trabajo construyendo algoritmos de análisis de caminos en redes. Concretamente en redes de proteínas dentro del metabolismo, donde cada nodo es una proteína y cada arista una interacción entre ellas en el organismo. Es interesante. Hay tantísimo sobre teoría de grafos, desde los típicos algoritmos de cálculo de caminos más cortos hasta los sorprendentes métodos de difusión de núcleo.

  3. Avatar
    Jeibros diciembre 13, 2012 at 9:07 am #

    Hace poco me tocó trabajar algo con estos grafos. Hay algoritmos concretos para resolverlos, pero no es ni tan siquiera eso lo suficiente, sino que hay que ver que esos algoritmos sean estables y convergentes... vamos, es un terreno todavía explorado. Creo que sobre todo se están empleando para modelar realidades y aplicando inteligencia artificial, resolver un problema, es decir, dotarles de inteligencia.

    Lo que a mí me llama la atención era el problema de computación. Es muy remoto que este tipo de problemas compense computacionalmente y que merezca la pena hacer los cálculos por fuerza bruta?

    • Avatar
      jorgejfrias diciembre 13, 2012 at 10:57 am #

      Te refieres a los grafos dinámicos ¿no? En efecto su estudio es demasiado reciente, y pienso que aún no contamos con las herramientas matemáticas necesarias para trabajar con ellos, aunque tengamos ordenadores cada día más potentes para simularlos.

      Sobre la segunda cuestión de tu comentario, la complejidad crece de forma exponencial a poco que añadimos un arco o un nodo, y cualquier problema práctico es mucho mayor que el de los puentes de Könisberg. Por otro lado, está la cuestión del tiempo: De nada sirve dejar días trabajando a un computador si necesita la respuesta en minutos. Sobre todo si basta con una solución satisfactoria aunque no sea la más óptima.

Trackbacks/Pingbacks

  1. Diciembre en HdC | Hablando de Ciencia | Artículos - diciembre 31, 2012

    [...] Grafos: Las Redes que mueven el mundo [...]

  2. Bitacoras.com - diciembre 13, 2012

    Información Bitacoras.com...

    Valora en Bitacoras.com: Las calzadas romanas, la red eléctrica y, recientemente, Internet. Todas las redes que el ser humano ha diseñado para su comunicación y progreso tienen algo en común: se pueden representar mediante grafos que nos ayudan a mod.....

Deja un comentario

Uso de cookies

Hablando de Ciencia usa cookies para la gestión de usuarios y para mejorar su experiencia. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies, pinche el enlace para mayor información.plugin cookies

ACEPTAR
Aviso de cookies