Archivo de autor

A.L. Barabási, el “hub” de las Redes Complejas

La Universidad Politécnica de Madrid acaba de conceder el doctorado “Honoris Causa”  a Alberto-Lázlo Barabási, uno de los principales investigadores en lo que se conoce como Ciencia de las Redes Complejas. Barabási es mundialmente conocido por su  modelo de formación de redes libres de escala, el cual ha sido utilizado para explicar el crecimiento y evolución de innumerables tipos de redes sociales, tecnológicas o biológicas, sin importar la naturaleza de las mismas. Como resultado, el artículo publicado en la revista Science en 1999 explicando el modelo de Barabási-Albert ronda ya las 10.000 citas, siendo uno de los artículos más citados en Science durante toda una década.

Hay que reconocer que el trabajo de Barabási, junto con el de Watts y Strogatz sobre las redes de pequeño mundo, ha sido uno de los precursores de una avalancha incontrolable de artículos sobre la caracterización de todo tipo de redes. Sin duda alguna, hay que reconocerle el mérito de ser uno de los “hubs” (nodos más conectados) más importantes dentro del campo de las Redes Complejas.

Fig.1.- Ejemplo de un red libre de escala. En este tipo de redes, la distribución de grado (número de conexiones de cada nodo) sigue una ley de potencia, lo que provoca la aparición de nodos altamente conectados (“hubs”).

 

Sin embargo, también es cierto que no todo el mundo ve a Barabási como el referente en el estudio de las redes complejas. El argumento principal de sus detractores es que su trabajo, a pesar de ser de una calidad y originalidad indiscutibles, está sobrevalorado. Y es que, paradójicamente, Barabási parece haber sido una afortunada víctima del “preferential attachment”, mecanismo que el mismo utilizó para explicar la aparición de redes libres de escala. Este fenómeno explica como los nodos más conectados de una red tienen una mayor facilidad para atraer nuevas conexiones hacia ellos, lo que en el campo de las redes sociales se llama “rich gets richer”.

En todo caso, desde este post felicitamos a Barabási por la mención recibida. Y aquí les dejo un link a la entrevista que concedió al periódico El País. Si no tienen tiempo para estudiar sus trabajos, lean esta entrevista, analicen el fondo de su mensaje y decidan si también quieren que Alberto-Lázlo Barabási sea su “hub” en lo que a Redes Complejas se refiere…

 

Fig.2.- Las redes libres de escala se basan en dos reglas fundamentales: a) están en continuo crecimiento y b) la probabilidad de adquirir nuevos enlaces (pi_i) depende del grado (k_i) de cada nodo.

 

Etiquetas: , , ,

La Estructura de las Redes Sociales

En la actualidad, y sobre todo gracias a internet, todos somos conscientes de la importancia de las redes sociales, no solo en la influencia que tienen sobre los individuos particulares, sino también como herramienta catalizadora de comportamientos sociales emergentes (como por ejemplo, el movimiento 15-M). Sin embargo, ¿somos conscientes de cual es la estructura de dichas redes?

Las redes sociales van mucho más allá de Facebook o Twitter, sin bien, estas dos redes on-line son un ejemplo paradigmático de red social. Como cualquier otro tipo de red, las redes sociales están formadas por dos elementos fundamentales: nodos y conexiones. En este caso, los nodos de la red son personas y las conexiones surgen de algún tipo de interacción entre dichas personas. Son ejemplos de red social la red de Facebook, cualquier red de e-mails, redes de llamadas telefónicas, la red de artista similares, redes de colaboración científica o las redes de contactos sexuales…

Imagen de previsualización de YouTube

Video: Red Social del Movimiento 15-M (Más información: http://15m.bifi.es ).

Siempre resulta peligroso generalizar, pero es cierto que la mayoría de las redes sociales comparten características estructurales, sin importar cual sea el origen de la interacción entre las personas que forman la red. Dicho en otras palabras, resulta inquietante observar como la estructura de la red de Facebook es muy predecible y que además, es muy parecida, por ejemplo, a la estructura de la red de contactos sexuales entre personas. Pero concretemos un poco más, ¿cuales son las características estructurales que se observan en las redes sociales?

A) Son redes libres de escala. Este concepto se refiere al número de conexiones que tiene cada persona de la red. Resulta que no tiene sentido definir un valor promedio, ya que el numero posible de “vecinos” de un nodo difiere en varios ordenes de magnitud. Es decir, hay personas son muy pocas conexiones pero también personas con muchísimas más conexiones de los esperado. Como consecuencia, es posible identificar en la red lo que se conoce como “hubs”, nodos muy conectados de especial relevancia en los procesos que puedan ocurrir en la red, como por ejemplo, cualquier proceso de transmisión de información.

B) Son redes con alto clustering. Contrariamente a las redes aleatorias, la probabilidad de que dos vecinos de un nodo estén conectados entre ellos es muy alta, lo que hace que sean redes muy densamente conectadas a nivel local (lo cual puede influir también en procesos de transmisión de información).

C) Son redes de “pequeño mundo” (small-world). ¿Cómo de alejados estamos unos de otros? Pues en realidad estamos más cerca de lo que creemos! Se estima que el número de pasos promedio entre cualquier persona del planeta está alrededor de 22 pasos. Hagan la prueba: ¿a cuantos pasos están de Obama? Yo conozco al Rector de mi universidad (1), el Rector conoce a Zapatero (2) y Zapatero conoce a Obama (3). Estoy a tres pasos del tipo más influyente del planeta! (por favor, tómenselo como un juego!)

D) Son redes con estructura de comunidad. Es decir, los nodos (personas, no lo olvidemos) tienden a agruparse en grupos fuertemente unidos. Pertenecer al grupo adecuado puede ser determinante en los procesos sociales que ocurren a nuestro alrededor. También es crucial poder tener acceso a varios grupos sociales.

E) Son redes asortativas. De acuerdo, está muy bien! Pero, ¿qué significa ser “asortativo”? Este término, acuñado hace tiempo por los sociólogos, hace referencia a la capacidad de los nodos de una red para agruparse con nodos parecidos a ellos. La consecuencia es que en las redes asortativas, como las redes sociales, los nodos muy conectados tienden a estar conectados entre ellos. ¿El peligro? Pues que desgraciadamente se crean lo que se conoce como “rich clubs”, es decir, grupos de nodos muy influyentes que interaccionan entre ellos, ¿pertenecen ustedes a un “rich club”? Enhorabuena, desgaciadamanete no es mi caso!

Todas estas propiedades, junto con otras, afectan de manera determinante a todos los procesos dinámicos que ocurren en una red social, como por ejemplo la difusión de opiniones o la transmisión de enfermedades. De todo ello hablaremos en una próxima entrada, pero mientras, para que se vayan entreteniendo, les dejo con la entrevista que nos realizaron recientemente en el programa de divulgación científica Universo Paralelo.

Etiquetas:

El Deterioro Cognitivo Leve bajo una nueva perspectiva

Un equipo de once investigadores del Centro de Tecnología Biomédica de la Universidad Politécnica de Madrid  formado por médicos, neuropsicólogos, ingenieros, físicos y matemáticos, ha dedicado parte del último año a intentar comprender, desde un nuevo punto de vista, cómo el deterioro cognitivo leve (DCL) influye en la compleja red de interacciones entre diferentes zonas cerebrales.

Esta enfermedad se manifiesta mediante pérdidas severas de memoria, tales como no recordar el camino de vuelta a casa o la pérdida repentina del hilo de una conversación. Aunque los individuos que sufren DCL pueden realizar la mayoría de las tareas cotidianas, un porcentaje muy elevado (entre el 10 y el 15% cada año) acaba desarrollando Alzheimer. Es por ello, que la comprensión de esta enfermedad, y sobre todo su evolución, preocupa significativamente.

El trabajo parte inicialmente de medidas de la actividad cerebral de un grupo de pacientes con DCL mediante magnetoencefalografía. Esta técnica permite medir con una alta resolución temporal el campo magnético generado por millones de neuronas situadas en la zona cortical (la más externa) del cerebro. Concretamente, se estudió dicha actividad durante una tarea de memoria, en la que los pacientes debían recordar una serie de letras que se les habían presentado con anterioridad. Seguidamente, se realizó el mismo tipo de experimento en un grupo de sujetos sanos, con el objetivo de comparar los resultados con un grupo de control.

La principal novedad de este trabajo radica en el método de análisis de las mediciones experimentales. Se obtuvieron las redes funcionales cerebrales de todos los sujetos mediante el cálculo de la sincronización entre las distintas zonas cerebrales. Los nodos de la red se correspondían con las diferentes zonas de la corteza cerebral, y las conexiones entre ellas dependían de la forma e intensidad en que estaba sincronizada la actividad electromagnética entre dichas zonas.

 


Fig.1.- Red Funcional de un paciente con Deterioro Cognitivo Leve.

Una vez obtenida la red compleja, su análisis topológico reveló resultados muy interesantes. En primer lugar, se observó que diferentes parámetros de red (camino medio, clustering, alcance, etc…) permitían diferenciar entre los sujetos de ambos grupos (pacientes y controles). Es decir, mediante el análisis topológico de la red funcional se podía detectar qué individuos habían desarrollado la enfermedad y cuáles no, con la suficiente bondad estadística.

Sin embargo, ¿qué nueva información se podía obtener sobre el Deterioro Cognitivo Leve? Es aquí donde el estudio realizó mayores avances. Por un lado, se observó que la red funcional de los sujetos que habían desarrollado la enfermedad se volvía mucho más activa, pero curiosamente lo hacía de manera aleatoria. Una de las sorpresas más significativas fue observar cómo las conexiones a larga distancia se incrementaban más de lo esperado, lo cual reducía el carácter modular de la red funcional.

El cerebro basa su funcionamiento en la combinación de un proceso de segregación de la información (determinadas zonas realizan determinadas tareas) más un proceso de integración (la información se comparte entre varias zonas). Los resultados del estudio mostraron cómo se rompía el sutil balance entre integración y segregación, aumentando en exceso las conexiones funcionales entre lóbulos y diluyendo, de esta manera, el carácter modular de la red.

Este tipo de técnicas de análisis, que se han empezado a utilizar en los últimos años, prometen aportar nuevos puntos de vista sobre distintas enfermedades cerebrales. En el Centro de Tecnología Biomédica de la UPM ya se está trabajando en cómo ligar los resultados obtenidos con la aparición de la enfermedad de Alzheimer en pacientes con DCL.

 

Artículo completo en www.plosone.org:

“Reorganization of Functional Networks in Mild Cognitive Impairment”, J.M. Buldú, R. Bajo, F. Maestú, N. Castellanos, I. Leyva, P. Gil, I. Sendiña-Nadal, J. A. Almendral, A. Nevado, F. del Pozo and S. Boccaletti, PLoS ONE 6(5): e19584. doi:10.1371/journal.pone.0019584.

 

 

Etiquetas:

Curso sobre Dinámica y Sincronización en Redes Biológicas

El tema no puede ser de más actualidad. Para poder comprender la dinámica de la mayoría de sistemas biológicos debemos tratarlos como una red de elementos en continua interacción. El objetivo de este curso es comprender como la estructura de dicha red de conexiones puede condicionar los procesos dinámicos que ocurren en ella.

 

El curso se llevará a cabo en las instalaciones provisionales del Centro de Tecnología Biomédica y contará con profesores de varios grupos de investigación de toda España. Aunque el nivel es post-doctoral, el curso se ha diseñado para poder ser seguido por alumnos sin conocimientos previos en este campo.

Aunque la inscripción ya se ha cerrado, es posible asistir como oyente enviando un correo a javier.buldu@ctb.upm.es

Etiquetas:
Categorias: General

Las Redes Complejas en el Universo Paralelo

Lo sabíamos desde hacía algún tiempo, pero no fue hasta el martes de la semana pasada en que las Redes Complejas dieron un salto al Universo Paralelo.

No se asusten, no hemos descubierto la puerta que nos permite pasar de un universo a otro (si lo hubiera). Simplemente hemos visitado el estudio de Radio Círculo, en el Círculo de Bellas Artes de Madrid. Allí, desde hace unos años, Oscar y Ana se dedican a acercar la ciencia a la sociedad mediante su programa semanal Universo Paralelo. Fue un placer conversar con ellos sobre Redes Complejas, intentando explicar en que consisten y cuales son sus posibilidades.

¿Qué no lo escucharon? No se preocupen, el audio del programa lo pueden oir en su página web o directamente en el siguiente link.

Desde aquí queremos dar las gracias a Oscar y Ana por invitarnos a contar en que estamos trabajando y, de paso, contagiarnos su entusiasmo por la divulgación científica.

Gracias!

Juan & Stefano & Javier

PS: El programa pasó volando! Queda pendiente otra visita para profundizar en el tema!

Etiquetas: , ,
Categorias: Divulgación, General

Las Redes Complejas y el Cerebro (II)

Lo prometido es deuda y hoy toca hablar de cómo la Teoría de Redes Complejas nos puede ser de utilidad para caracterizar enfermedades relacionadas con la actividad cerebral y, tal vez, detectarlas antes de que se manifiesten.

Hemos comentado en entradas anteriores como los métodos de análisis de redes nos han permitido obtener nueva información sobre diversos tipos de redes biológicas, tales como las redes de interacción genética, redes de proteínas o redes metabólicas. La aplicación de estas técnicas al análisis de las disfunciones en la actividad cerebral es bastante reciente, ya que no fue hasta el año 2005 cuando aparecieron los primeros artículos sobre cómo una alteración de la estructura de la red funcional podía estar ligada a la manifestación de una determinada patología.

A día de hoy queda mucho por hacer, pero ya disponemos de los primeros resultados en enfermedades como el deterioro cognitivo leve, la esquizofrenia, la epilepsia o el Alzheimer. A pesar de que cada una de estas enfermedades posee sus propias particularidades, todas ellas comparten algo en común: la estructura de las conexiones entre los nodos (ciertas regiones del cerebro) de la red funcional ha variado respecto a la estructura de las redes de sujetos sanos.

¿A qué nos referimos cuando decimos que la estructura de la red varía?

Tradicionalmente, la caracterización de las redes cerebrales se realiza a tres niveles: macroscópico, mesoscópico y microscópico. A nivel macroscópico se estudian propiedades de la red global, como por ejemplo, como de aleatoria es su distribución de conexiones, cual es el número medio de pasos que existen para ir de un nodo a otro o como de densa es la red localmente (mediante el coeficiente de clustering). A nivel mesoscópico lo que se hace es detectar la comunidades existentes dentro de la red (si las hubiera), las cuales consisten en grupos de nodos altamente conectados entre si. Una vez detectada la estructura de las comunidades, se estudia si existe solapamiento entre ellas y cómo es el flujo de información inter-comunitario. Finalmente, a nivel microscópico, se intenta detectar cuales son los nodos centrales (más importantes) de la red, pero no solo aquellos que están más conectados, si no también qué nodos son los responsables de la comunicación entre las distintas comunidades de la red.

Todas estas propiedades pueden medirse en redes funcionales de pacientes que sufran una determinada patología, obtenidas, por ejemplo, mediante magnetoencefalografía durante una tarea cognitiva concreta. A continuación, se pueden buscar las diferencias con los resultados obtenidos en un grupo de individuos sanos.

Figura 1.- Ejemplo de la variación de la estructura de una red funcional debida a una determinada patología: red funcional de un paciente con esquizofrenia (B) y un individuo sano (A). Obtenida de Basset et al., J. Neoroscience, 28, 9239 (2008).

Como comentamos, los resultados publicados hasta la fecha son muy prometedores. En pacientes con esquizofrenia se ha observado como su red funcional se vuelve más aleatoria, perdiendo a la vez la jerarquía observada en las redes de sujetos sanos. En epilepsia los resultados van en la dirección contraria, ya que la red funcional se vuelve más activa y regular, perdiendo la complejidad inherente de las redes cerebrales. En enfermedades que afectan a la memoria, tales como el deterioro cognitivo leve o el Alzheimer, los resultados también son significativos. Se puede observar claramente como los individuos que sufren deterioro cognitivo leve (perdidas severas de memoria) tienden a realizar un sobre esfuerzo para poder realizar cualquier tarea de memoria, lo que resulta en una red funcional más conectada, pero con un mayor coste energético. En pacientes con Alzheimer, por el contrario, se observa un fenómeno de desconexión junto con un aumento del carácter aleatorio de la red.

Este tipo de estudios nos permitirán añadir nueva información a lo (poco) que sabemos sobre las enfermedades cerebrales, sin embargo, no debemos de olvidar nunca la característica fundamental de este tipo de sistemas: cada cerebro es distinto (¿se imaginan lo contrario? Que horror!).

 

PS: Si les interesa el tema, no dejen de visitar este link. También se pueden bajar un seminario impartido por este humilde y desorganizado autor en la UPM, allí encontrarán más información y varias referencias clave.

 

Etiquetas: ,

Las redes complejas y el cerebro (I)

Hoy toca hablar de uno de los sistemas biológicos más intrigantes a que nos enfrentamos: el cerebro. Y es que probablemente durante las próximas décadas nuestro conocimiento sobre el cerebro (humano o no) vaya a avanzar considerablemente. Mucho nos jugamos en ello, ya que el aumento de la esperanza de vida ha disparado la incidencia de enfermedades cerebrales, convirtiéndose en uno de los principales focos de atención en investigación médica. Se preguntarán que pueden aportar las herramientas metodológicas desarrolladas en el marco de las Redes Complejas al estudio del cerebro. Yo pienso que mucho, pero déjenme que les explique porque…

Seguro que todos conocen el programa de televisión, Redes, donde el carismático divulgador científico Eduard Punset nos recuerda cada semana lo apasionante que puede ser la ciencia. Los que lo sigan, habrán comprobado el tiempo que se dedica a explicar tanto el funcionamiento del cerebro como sus consecuencias en la actividad vital de las personas. Y es que el cerebro es una gran RED formada por miles de millones de neuronas (se estima que alrededor de cien mil millones).

Sin embargo, ¿cuál es principal problema a la hora de analizar dicha red?  Pues que no disponemos actualmente de una tecnología que nos permita obtener la compleja red de interacciones entre neuronas de un cerebro humano, ya sea en plena actividad o diseccionado encima de una mesa. Esta limitación aparecerá siempre en cualquier estudio sobre anatomía o dinámica cerebral, sin embargo, podemos intentar buscar aproximaciones que nos permitan obtener alguna información sobre lo que está pasando dentro de nuestras cabezas…

¿Cómo obtener una red cerebral?

Principalmente existen dos vías paralelas: por un lado, podemos realizar una parcelación de las diferentes regiones del cerebro, obtener sus conexiones físicas mediante un estudio histológico o análisis de imagen y obtener así lo que se conoce como una Red Anatómica. Por otro lado, podemos medir la dinámica de distintas zonas del cerebro durante una actividad cognitiva o motora (mediante resonancia magnética funcional, electroencefalografía o magnetoencefalografía), buscar las relaciones o dependencias que existen entre las distintas zonas analizadas y obtener así una Red Funcional.

Figura 1.- Como obtener una red cerebral (anatómica o funcional). Obtenida de  Bullmore et al., Nature, 10, 186 (2009).

Una vez obtenida la red, es el momento de comenzar analizarla bajo la perspectiva de las redes complejas. Las posibilidades son muchas, desde cuantificar cual es la eficiencia en la transmisión de información dentro la red, detectar la existencia de comunidades o clusters que realizan una determinada función, analizar la robustez de la red frente a fallos aleatorios o selectivos, o cuantificar la importancia (centralidad) de cada uno de los nodos.

Sin embargo lo más importante es comprender qué nueva información nos puede aportar este tipo de análisis. La respuesta es doble, ya que por un lado, nos permite comprender mejor como se reorganizan las redes funcionales cuando realizan una determinada actividad cognitiva y cual es su relación con la red anatómica subyacente. Por otro lado, nos permite comparar el estado de las redes obtenidas en sujetos sanos con aquellas provenientes de pacientes con una determinada patología. De esta manera, es posible obtener nueva información sobre el origen y desarrollo de distintas enfermedades cerebrales.

Prometo profundizar más en el tema, pero eso será la semana que viene…

PS: … si han llegado hasta aquí es que tal vez les interese el tema. Les dejo un seminario, impartido recientemente en la Universidad Politécnica de Madrid, que profundiza más en este tipo de estudios. De él hablaremos en la próxima entrada.

Etiquetas:

Los amigos de mis amigos son mis amigos

Desde la perspectiva de un científico, el análisis del comportamiento humano puede ser uno de los problemas más desesperantes como materia de estudio, ¿por qué nos comportamos de una determinada manera? ¿cuándo cambiamos de opinión? ¿cómo influyen otras personas en nuestra toma de decisiones? Una de las posibles respuestas sería “cada uno es como es”, es decir, poco podemos hacer por cambiar el comportamiento o parecer de una determinada persona. Sin embargo, el problema puede volverse mucho más sencillo simplemente con… complicarlo un poco!

A pesar de la heterogeneidad de comportamientos de los seres humanos, estos actúan siguiendo patrones muy parecidos cuando se les coloca dentro de una red de interacción con otros individuos. El estudio de las redes sociales, desde el punto de vista de cómo la estructura de la red puede influenciar en el comportamiento de las personas, lleva más de un siglo cautivando el interés de sociólogos, psicólogos y antropólogos [1], y más recientemente de matemáticos y físicos. Hemos hablado ya en este blog de los trabajos de Stanley Milgram mostrando la propiedad de “pequeño mundo” en las redes sociales [2], la cual hace que estemos a muy pocos pasos de individuos que en principio nos podrían parecer muy alejados tanto socialmente como físicamente. Resulta también curioso observar como en muchos casos incluso relaciones de baja intensidad con otros individuos pueden influenciarnos enormemente. En este aspecto, Mark Granovetter fue uno de los pioneros en estudiar la importancia de los “enlaces débiles” [3], sorprendido por la cantidad de personas que decían haber encontrado trabajo mediante un simple conocido.

clustering

Pero en la entrada de hoy me gustaría resaltar un trabajo publicado recientemente en la revista Science sobre como se difunde por una red social una determinada idea o comportamiento [4]. En este artículo Damon Centola construye una comunidad de usuarios de internet con intereses sobre temas de salud. La particularidad de este trabajo es que cada usuario puede ver la actividad y opiniones de unos pocos miembros de la red, los cuales son elegidos directamente por el autor del trabajo, configurando así redes de distintas topologías (small-world o alto clustering). Los resultados son sorprendentes, contrariamente a lo que se pensaba, la existencia de conexiones a larga distancia no fomenta la propagación de información en la red. Sin embargo, el clustering resulta ser fundamental. Este termino (clustering) mide la densidad local de las conexiones analizando si los vecinos de un determinado individuo son también vecinos entre sí. De esta manera, si en nuestra red de amistades, éstas son a su vez amig@s entre ellos, tendremos un clustering alto. Centola observa en sus experimentos que es mucho más fácil transmitir una idea o un cambio de comportamiento en redes con alto clustering, y explica que es debido a la realimentación que se produce en este tipo de estructuras. Si lo pensamos, resulta bastante razonable: si un amigo nos intenta convencer sobre un determinado asunto, puede que le hagamos caso (o no), pero si ya son dos, la probabilidad de convencernos es mucho más alta. Curiosamente, uno de los resultados del artículo es que es precisamente dos el número de interacciones óptimas para cambiar un determinado comportamiento, es decir, en caso de recibir muchos mas inputs, éstos ya no tendrán la eficacia de los dos primeros, ¿realmente somos tan previsibles? Lean el artículo de Centola.

[1] L. Freeman, The Development of Social Network Analysis. Vancouver: Empirical Press (2006).

[2] S. Milgram, “The Small World Problem”, Psychology Today, 1, 60 – 67 (1967).

[3] M. Granovetter, “The strength of the weak ties”, American JOrunal of Sociology, 78, 1360-1380 (1973).

[4] D. Centola, “The spread of Behavior in an Online Social Network Experiment”, Science, 329 (5996), 1194-1197 (2010).

Etiquetas: , , ,
Categorias: General

Para comenzar, hablemos un poco de Euler

Es casi una obligación comenzar este Blog sobre Redes Complejas hablando de Leonard Euler, ya que es considerado el padre de la Teoría de Grafos. Euler nació en Basilea en 1707 y fue, junto con Paul Erdös (del que hablaremos próximamente), uno de los matemáticos más prolíficos de la historia. Es de destacar que trabajara en casi todas las disciplinas de las matemáticas, desde geometría, cálculo o  trigonometría, hasta álgebra y teoría de números, realizando incluso diversas incursiones en el campo de la física.

Leonard Euler

Figura 1.- Leonard Euler (Basilea 1707, San Petersburgo 1783). Se puede observar en la imagen cómo uno de sus ojos ya le comenzaba a fallar. Acabaría perdiendo totalmente la visión, lo cual no le impidió seguir investigando y publicando trabajos de gran impacto científico.

Pero vayamos a la historia que, según cuenta la leyenda, dio lugar al origen de la Teoría de Grafos (y más adelante a lo que se conocería como Redes Complejas). A principios del siglo XVII, Königsberg (actualmente Kaliningrado, Rusia) era una tranquila ciudad de la Prusia Oriental. Como muchas otras ciudades europeas, estaba atravesada por un río, el Pregel, que dividía la ciudad en dos mitades, a las que había que sumar dos pequeñas islas debidas a una bifurcación del río.  Para facilitar el paso de una parte a otra de la ciudad, así como a cada una de las islas, se habían construido un total  de siete puentes. El problema de los puentes de Königsberg era sencillo en su planteamiento: ¿es posible visitar a pie todas las zonas de la ciudad, volviendo al punto de partida, pero pasando una única vez por cada puente?

La respuesta es sencilla si se dispone de tiempo y paciencia, ya que se pueden calcular todas las posibles combinaciones de paso por los puentes para llegar a la conclusión de que no es posible: siempre hay que pasar dos veces por uno de los puentes. Como digo, la solución ya era conocida, sin embargo, el mérito de Euler fue encontrar una solución sencilla y elegante, que resolvía no solo el dilema de los puentes de Königsberg, sino también casos mucho más generales. Solo había que transformar a la ciudad y sus puentes en una red.

como proyectar...

Figura 2.- Como proyectar el entramado de puentes de Königsberg en una red.

Si se considera cada una de las zonas de la ciudad como un nodo y cada uno de los puentes que las une como un enlace, es posible obtener una red de 4 nodos y 7 enlaces (ver Figura superior). A partir de ahí, es sencillo demostrar que si queremos iniciar y finalizar el camino en el mismo punto necesitamos dos requisitos: a) que los nodos por los que pasemos tengan un número par de enlaces y b) que en el caso de tener un nodo con un número impar de enlaces, este debía ser el inicio (y final) de nuestro camino. Desgraciadamente, Königsberg no cumplía el primer requisito.

Y fue con este ejemplo tan curioso como Euler creó, sin saberlo, lo que se conoce hoy en día como la Teoría de Grafos. Es interesante como, una vez más, se repite el mecanismo que permite a la ciencia dar saltos de gigante:  si tenemos un problema, ataquémoslo desde  nuevos puntos de vista.

Como curiosidad, Kaliningrado, la antigua Königsberg, conserva hoy en día solo cinco de sus puentes (es lo que tienen las guerras mundiales!). Sin embargo, todavía no es posible realizar lo que se conoce como un “ciclo euleriano”…

Etiquetas: ,