‘Investigadores’

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: , , ,

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: ,