PDF de programación - Redes, Interacciones, Emergencia

Redes, Interacciones, Emergencia

Lucas Lacasa, Universidad Politécnica de Madrid, Espa ña

Tenemos la física de lo muy grande, la física de lo muy peque ño ... y la física de lo mucho. Y en este
último caso, parece fundamental el conocer cómo está conectado ese mucho. Pues finalmente, el
todo es más que la suma de sus partes porque las partes no suman, simplemente. Se agregan en un
enjambre de interconexiones. La arquitectura de la complejidad.

1.

Introducci ón

La tradici ón en ciencia, ya sea en física o en biología, ha sido hasta la fecha eminente-
mente reduccionista: romper el problema en sus ladrillos básicos y encontrar la soluci ón
como una sencilla extrapolaci ón lineal del comportamiento individual. Como se ha puesto
de manifiesto en la parte tercera de este libro, este enfoque reduccionista, a ún cuando los
logros y el avance científico asociado son incuestionables, es ineficiente cuando el sistema
bajo estudio está formado por un alto n úmero de elementos que interaccionan de forma
no lineal entre sí. El comportamiento complejo emerge de la agregaci ón de estos elementos
y para una correcta descripci ón de las propiedades macrosc ópicas del sistema se antoja
necesario estudiar el sistema en su totalidad, describiendo tanto las propiedades locales
e individuales de cada elemento como la arquitectura que emerge de las interconexiones
y agregaci ón del conjunto. Ejemplos existen por doquier: así como el cambio dramático
que evidencia el agua al reducir la temperatura de la misma por debajo de 0◦ Celsius no
puede explicarse únicamente a partir del estudio de las propiedades físico-químicas de
la molécula H2O, la extinci ón de especies en un ecosistema no puede entenderse a partir
de las relaciones de predaci ón o mutualismo entre dos especies separadas de su entorno.
Es la arquitectura formada por las interacciones entre las moléculas de agua, o la formada
por las interacciones entre cada especie que constituye un ecosistema, la que nos abre las
puertas al entendimiento de los fen ómenos colectivos (transiciones de fase, extinciones
en cascada) que acaecen en el seno de esos sistemas. En los últimos a ños, un auténtico
cambio de paradigma en la forma de entender los sistemas complejos está emergiendo, al
constatar que una forma natural de describir dicha arquitectura es mediante un aparato
matemático denominado red. Una red, formada por elementos (nodos) conectados entre

4

Redes, Interacciones, Emergencia

sí por enlaces que cuantifican la interacci ón entre ellos. Aunque las herramientas para
describir estos objetos -denominados grafos en la comunidad matemática- fechan de me-
diados del siglo pasado, no es hasta el principio del siglo XXI cuando esta aproximaci ón
se consolida como fundamental para el estudio y la descripci ón de sistemas complejos
que muestran comportamiento emergente. La raz ón de este desfase es bien sencilla: el ac-
ceso a datos empíricos (experimentos) con los que construir dichas redes no fue posible
hasta hace pocos a ños, cuando la capacidad de procesamiento y c ómputo de los ordena-
dores experimentase un crecimiento explosivo. Vivimos pues en la era de los datos. Con
la ayuda de los ordenadores, modelos te óricos de interacci ón en red se están viendo com-
probados diariamente. Y como no, cada respuesta plantea muchos otros interrogantes.
¿Qué informaci ón de un sistema complejo puede extraerse de la arquitectura que emerge
de su red de interacciones?, ¿Qué relevancia tiene esta arquitectura en el comportamien-
to dinámico del sistema?, ¿Qué tipo de arquitecturas podemos encontrarnos en las redes
de interacci ón?, ¿Por qué? En este capítulo trataremos de dar respuesta a algunas de estas
cuestiones, haciendo un buceo en el mundo de las redes complejas y su aplicaci ón en dife-
rentes problemas, desde la transmisi ón de epidemias o los algoritmos de b úsqueda hasta
la extinci ón de especies. Acabaremos el capítulo planteando cuál puede ser el devenir de
esta rama científica, cuyo progreso actual es exponencial y cuyo potencial está práctica-
mente limitado únicamente por nuestra imaginaci ón.

2. Redes complejas: definiciones y ejemplos

Los inicios

Los orígenes de la teoría de redes están relativamente desperdigados en el tiempo.
El trabajo seminal, denominado el los siete puentes de K ¨onigsberg, data del siglo XVIII
y fue planteado por el gran matemático Leonard Euler. En aquel entonces, la ciudad de
K ¨onigsberg (el antiguo nombre que recibía la actual ciudad rusa de Kaliningrado), que
durante el siglo XVIII formaba parte de Prusia Oriental, era atravesada por el río Pregol-
ya, el cual se bifurcaba generando una peque ña isla en el centro de la ciudad y dividiendo
a la misma en cuatro partes separadas por agua y únicamente conectadas por un total de
siete puentes. El problema que Euler se planteaba era saber si era posible el encontrar un
circuito que pasara por cada uno de los puentes de esta ciudad, de tal forma que el cami-
nante regresara al mismo punto habiendo atravesado cada uno de los siete puentes una
vez y una sola. La respuesta fue negativa: no existe una ruta con estas características. Para
hallar esta soluci ón, Euler necesit ó formalizar el problema en términos de un conjunto
abstracto de nodos conectados entre si por otro conjunto de enlaces, que caracterizan las
regiones terrestres y las conexiones entre ellas (ver figura 1), y analizar las propiedades de
este constructo. Su demostraci ón no solo dio lugar al nacimiento de una nueva rama en
matemática discreta, la teoría de grafos, sino que la generalizaci ón del resultado de Euler
en poliedros convexos dio lugar de la mano de Cauchy a la topología.

Lucas Lacasa

5

Figura 1: A la izquierda vemos el problema de los siete puentes de K ¨onigsberg, y a la derecha
la abstracci ón matemática del mismo en términos de nodos (regiones de tierra) conectados por
enlaces.

Figura 2: Grafos con diferentes topologías.

Tuvo que pasar casi un siglo, para que el matemático Cayley, que se hallaba estudiando
ciertos problemas de cálculo diferencial, se topase en sus pesquisas con ciertas estructuras
parecidas a las abstracciones de Euler: un tipo concreto de grafos denominados árboles
(grafos acíclicos). Estos resultados tuvieron muchas aplicaciones en la química de la época.
A partir de entonces, la teoría de grafos como disciplina matemática con derecho propio
tuvo un auge importante, de la mano de científicos como Polya, Sylvester (quien introdujo
la palabra grafo), Jordan o Kuratowski.

La teoría de grafos, hasta mediados del siglo pasado, estudiaba objetos que no consta-
ban más que de un pu ñado de nodos (ver ejemplos en la figura 2). Con el desarrollo de las
teorías de la probabilidad y la estadística, una nueva vía de estudio en la teoría de grafos
tuvo lugar en los a ños sesenta del siglo pasado, de la mano del gran matemático Paul
Erd ¨os. Para los intereses de la subsiguiente teoría de redes este fue el punto de arranque,
pues los métodos probabilísticos permitieron estudiar por primera vez las propiedades
de grafos arbitrariamente grandes, cambiando ligeramente el enfoque y adquiriendo una

6

Redes, Interacciones, Emergencia

Figura 3: Proceso de formaci ón de redes bajo el modelo Erd ¨os-Renyi.

aproximaci ón estadística. Como concepto opuesto al grafo regular (grafo donde cada no-
do se conecta a k vecinos), emerge de la mano de Erd ¨os y su colaborador Renyi el concepto
de grafo aleatorio, o grafo de Erd ¨os-Renyi, como aquel grafo generado por un proceso es-
tocástico donde en cada paso dos nodos cualesquiera se conectan con cierta probabilidad
p (ver figura 3). Estas aproximaciones te óricas se vieron muy beneficiadas a finales de los
a ños noventa con la llegada de los ordenadores modernos, capaces de manejar una gran
cantidad de datos. El estudio estadístico de grafos ya no residía únicamente en desarro-
llos formales. Los grafos reales, tales como la red de redes (internet) o las redes sociales o
biol ógicas pudieron, por primera vez, ser examinadas y sus propiedades estadísticas cal-
culadas. Y los resultados no pudieron ser más inesperados: se encontraron con que estas
arquitecturas eran extremadamente más complejas de lo que la teoría de Erd ¨os describía.
Sin embargo, dentro de ese caos de conexiones, ciertos patrones de orden emergían. La
nueva era de la teoría de grafos, el análisis de grafos enormes que no eran ni regulares ni
aleatorios, se llam ó la teoría de redes complejas. Pasen y vean.

Ejemplos de redes complejas

Existen multitud de tipos de redes: algunas son no dirigidas (donde los enlaces no tie-
nen direcci ón preferente), otras que si lo son, otras donde existen realmente dos conjuntos
bien diferenciados de nodos (redes bipartitas), otras donde cada enlace ha de ser pesado
seg ún la importancia del mismo, y así sucesivamente. En este capítulo no vamos a discri-
minar estas características y por sencillez nos centraremos en el caso más general de redes
no dirigidas. A continuaci ón, y a modo de casos ilustrativos, enumeramos una lista no
exhaustiva de algunas de las redes complejas que podemos observar a nuestro alrededor.

Lucas Lacasa

7

Figura 4: Red de internet.

Redes de informaci ón

WWW: es la red más grande que ha sido analizada hasta el momento. Los nodos de
esta red los conforman las páginas web, y dos nodos están conectados por un enlace
si existe un hyperlink en una página que apunta a la otra. Esta red ha tenido un
proceso de crecimiento descentralizado y autoorganizado, por lo que su descripci ón
es de especial interés bajo el paraguas de los sistemas complejos.

Internet: dependiendo del nivel de estudio, se define como una red donde los no-
dos son (i) computadoras o routers enlazados entre sí físicamente, o (ii) sistemas
aut ónomos (compuestos de cientos de routers y computadoras) enlazados entre sí.
De especial inter