En la actualidad las redes complejas se estudian por su relación con muchos campos de la ciencia. Sin duda, muchos sistemas en la naturaleza se pueden describir por medio de redes complejas, que topológicamente son grafos (estructuras matemáticas formadas por nodos (o vértices) conectados por enlaces (o aristas)) a los que se agregan algunas características dinámicas que hacen necesario estudiarlos desde varios puntos de vista.

Los ejemplos de la presencia de las redes complejas en la vida real son numerosos; por ejemplo, Internet es una red de routers o dominios conectados por líneas físicas, la World Wide Web es una red de sitios web conectados por hiperenlaces, el cerebro es una red de neuronas conectados por medio de las sinapsis, una organización es una red de personas con diversos tipos de conexiones entre ellas, la economía mundial es una red formada por las economías nacionales, que a su vez son redes de mercados, y éstos son redes de productores y consumidores que interactúan, las redes alimentarias y las rutas metabólicas pueden ser representadas por redes, así como las relaciones (semánticas o sintácticas) entre las palabras de un idioma, los temas en una conversación, e incluso las estrategias para resolver un problema matemático o las redes culturales en las que se mueven los objetos e ideas generadas por el hombre. Hasta aquí nos quedaríamos con la representación de estos sistemas por medio de la estructura de grafo matemático, pero si consideramos por ejemplo las enfermedades que se transmiten a través de redes sociales, los virus informáticos que en ocasiones se extienden a través de la Internet, o la energía que se distribuye a través de las redes de transporte, nos damos cuenta de que, junto a esa estructura organizativa en forma de grafo es importante conocer la dinámica que se produce en el flujo de información a través de ella, o incluso la dinamica que se puede producir en la evolución temporal de dicha estructura, que a menudo no es fija ni en el conjunto de nodos que interviene ni en las conexiones que se producen entre ellos.

La ubicuidad de las redes complejas, es decir, su aparición con características similares en muchas áreas de conocimiento, ha llevado de forma natural al establecimiento de un conjunto de problemas de investigación, comunes e importantes en todas esas áreas, relativos a la forma en que la propia estructura de la red facilita y limita los comportamientos dinámicos de la misma, y que en gran medida han sido descuidados en los estudios de las disciplinas tradicionales, posiblemente por la ausencia de una teoría matemática que permitiera abordarlos y la incapacidad técnica de almacenar y manipular las grandes cantidades de datos asociadas a cada una de esas redes. Algunas de estas preguntas para redes concretas son: ¿cómo interviene la estructura de las redes sociales en la transmisión de una enfermedad? ¿Cómo se propagan fallos en cascada a través de una red de transmisión de energía o de una red financiera global? ¿Cuál es la arquitectura más eficiente y robusta para una organización particular bajo un entorno cambiante e incierto?

Durante más de un siglo, el modelado de muchos de estos procesos y sistemas se ha realizado bajo la suposición implícita de que los patrones de interacción entre los elementos del sistema podían ser representados por medio de una estructura regular al estilo de un retículo euclídeo. A finales de 1950, dos matemáticos, Erdös y Rényi (ER), hicieron un gran avance en la teoría matemática clásica de grafos que revolucionaría la forma en que se pueden modelar estos problemas describiendo una red con topología compleja por medio de un grafo aleatorio, estableciendo los fundamentos de la teoría de redes aleatorias. Aunque la intuición indica claramente que muchas redes complejas de la vida real no son ni totalmente regulares ni completamente aleatorias, el modelo ER fue el único enfoque sensato y riguroso que dominó el pensamiento de los científicos acerca de las redes complejas durante la segunda mitad del siglo XX.

En los últimos años, gracias a la automatización del proceso de adquisición de datos y a las herramientas computacionales generadas para el tratamiento posterior de estos datos, se tiene capacidad para trabajar sobre grandes bases de datos relativas a muchas y variadas redes complejas. Además, el acceso público a esta enorme cantidad de datos ha estimulado un gran interés por tratar de descubrir las propiedades genéricas de los diferentes tipos de redes complejas a las que podemos acceder. En este sentido, los descubrimientos del efecto de mundo pequeño y la característica de libre de escala de la mayoría de las redes complejas han sido especialmente significativos y supusieron un avance más en el estudio de estas redes.

En 1998, con el fin de describir la transición de una red regular en una red aleatoria, Watts y Strogatz (WS) introdujeron el concepto de red de mundo pequeño. Debe notarse que el fenómeno de mundo pequeño es de hecho muy común, y nada alejado de nuestras experiencias diarias. A menudo, poco después de conocer a un extraño, uno se sorprende al descubrir que tenemos un amigo común con él, de modo que es habitual la expresión: "¡Qué pequeño es el mundo!". Un experimento que se realizó hace más de 40 años dio lugar al llamado "principio de los seis grados de separación", sugerido por el psicólogo social Milgram a finales de 1960, y que establece que entre cualesquiera dos personas del mundo hay una media de 6 conexiones de amistad, independientemente de lo lejanas que estén dichas personas. Aunque este punto sigue siendo controvertido, el patrón del mundo pequeño ha demostrado estar presente en muchas redes reales. Una característica importante y común al modelo de redes aleatorias (ER) y al de mundo pequeño (WS) es que la función de distribución de grados tiene un máximo en el valor medio del grado y decae exponencialmente, lo que quiera decir que casi todos los nodos de la red tienen el mismo número de conexiones. Por ello, es común denominar a estos tipos de redes de manera conjunta como redes exponenciales o redes homogéneas.

Otro descubrimiento fundamental en el ámbito de las redes complejas, y que supuso un hito al reconocer de qué forma podíamos enfrentarnos a ellas, fue la observación de que muchas son libres de escala, es decir, la función de distribución de grados sigue una ley de potencias, que es independiente de la escala de la red. A diferencia de una red exponencial, una red libre de escala es no homogénea: la mayoría de los nodos tienen muy pocas conexiones y, hay unos pocos nodos que tienen muchas, de forma que los nodos no se agrupan alrededor de un valor medio característico.

Algunos conceptos básicos

Aunque se han propuesto e investigado en las últimas décadas muchas medidas cuantitativas de redes complejas, hay tres conceptos que juegan un papel clave: la longitud media de los caminos, el coeficiente de clustering, y la distribución de grados. Debido a la imposibilidad de manejar la información de las redes de una forma individual para los nodos, era necesario definir algunas medidas globales que permitieran caracterizar las redes con el fin de poder comparar la similitud entre ellas, así como la adecuación de los diversos modelos matemáticos con las redes reales que pretende modelar. De hecho, el intento inicial de Watts y Strogatz en su trabajo de redes de mundo pequeño fue la construcción de un nuevo modelo matemático que permitiera construir redes con longitudes medias de caminos pequeñas, tal y como ocurre en los grafos aleatorios, y que tuvieran un coeficiente de clustering relativamente alto, como ocurre con las redes regulares. Por otro lado, la generación de modelos que creen redes libres de escala se basa en la observación de que las distribuciones de grado de muchas redes reales siguen una forma similar a una ley de potencias. Ha de indicarse que, debido a la alta complejidad de las redes reales, no se han encontrado todavía caracterizaciones completas de las mismas, es decir, en la actualidad todavía no disponemos de un conjunto de medibles que caractericen por completo a cada red (algo así como un código genético que nos permita con absoluta precisión establecer comparaciones entre ellas). 

Longitud promedio de los caminos

El conjunto de definiciones relacionadas con la medición de distancias internas que necesitamos son:

• La distancia \(d_{ij}\) entre dos nodos (\(i\) y \(j\)) se define como el número de enlaces del camino más corto que los conecta.
• El diámetro, \(D\), de la red se define como la máxima distancia entre cualesquiera par de nodos de la red.
• La longitud promedio, \(L\), se define como la media de las distancias entre todos los pares de nodos, es decir, la separación típica entre pares de nodos.

A medida que se tenían más datos de redes complejas reales se constató que la longitud promedio de los caminos de la mayoría de ellas era relativamente pequeña, incluso en los casos en que estos tipos de redes tuvieran muchos menos enlaces de los posibles que se podrían dar (a menor cantidad de conexiones en el mundo, parece claro que haya que hacer recorridos más largos para poder llegar de un nodo a otro). Esta característica es lo que se llamó efecto de mundo pequeño, y de ahí el nombre de redes de mundo pequeño que intentan modelarlo.

Coeficiente de Clustering

En tu red de amigos es muy posible que los amigos de tus amigos sean también amigos tuyos. Esta propiedad se refiere a la agrupación (o clustering, por su nombre en inglés) de la red. Más precisamente, podemos definir un coeficiente de clustering \(C\) como la proporción media de pares de vecinos de un nodo que también son vecinos entre sí.

Supongamos que un nodo \(i\) de la red tiene \(k_i\) vecinos (o enlaces). Es evidente que, a lo sumo pueden existir \(k_i (k_i - 1) / 2\) enlaces entre ellos (y esto solo ocurre si todos están conectados entre sí). El coeficiente de clustering, \(C_i\), del nodo \(i\) se define entonces como la proporción entre, \(E_i\), el número de enlaces que de verdad existen entre los vecinos de \(i\), y la máxima cantidad posible, es decir:

\[C_i=\frac{E_i}{k_i (k_i - 1) / 2}\]

El coeficiente de clustering de la red será la media de los coeficientes de clustering de todos sus nodos. Obviamente, \(C\leq 1\) y solo tomará el valor \(1\) en el caso de que la red sea completa (es decir, aquella que tiene todas las posibles conexiones entre todos sus nodos). En una red completamente aleatoria de \(N\) nodos se puede probar que \(C \sim 1 / N\), un valor que sería muy pequeño en la mayoría de las redes reales, que tienen un número muy elevado de nodos. Sin embargo, se ha constatado numéricamente que la mayoría de las redes reales tienen tendencia a la agrupación, en el sentido de que sus coeficientes de clustering son mucho mayores que \(O(1/N)\), a pesar de ser significativamente menores que \(1\), de donde podemos inferir que la mayoría de las redes complejas reales no son ni aleatorias ni completas.

Distribución de Grados

La más simple, y quizás también la más usada, característica individual de un nodo es su grado. El grado, \(k_i\), de un nodo \(i\) se define generalmente como el número total de sus conexiones. El promedio de los grados de los nodos de una red se llama grado medio de la red, y se denota por \(\bar{k}\).

La distribución de grados de los nodos en una red viene dado por la función de distribución \(P(k)\), que es la probabilidad de que un nodo seleccionado al azar tenga exactamente \(k\) enlaces. Una red regular tiene una distribución de grados muy simple, porque todos los nodos tienen el mismo número de enlaces, por lo que su gráfica vendría representada por una distribución de tipo delta (es decir, la función se anula para todos los posibles grados, menos para el grado que tienen todos sus nodos, donde se alcanza el valor \(1\)). Cualquier aleatoriedad en la red ampliará la forma de este pico, y en el caso límite de una red completamente aleatoria, la distribución de grados sigue una distribución de Poisson, donde la forma de la distribución cae de manera exponencial a medida que nos alejamos del valor máximo, \(\bar{k}\). Debido a este descenso exponencial, la probabilidad de encontrar un nodo con \(k\) enlaces se convierte en insignificante para \(k >> \bar{k}\).

En los últimos años, muchos resultados empíricos muestran que en la mayoría de las redes reales de gran escala el grado de distribución se desvía significativamente de la distribución de Poisson. En particular, para muchas redes el grado de distribución se describe mucho mejor por una ley de potencias de la forma \(P(k) \sim k^{-\gamma}\). Esta distribución cae de forma más gradual que una exponencial, lo que permite la existencia de algunos nodos de grado muy alto. Debido a que estas leyes de potencia no se concentran alrededor de una media (escala), es por lo que se llaman libres de escala.

Modelos de Redes Complejas

Medir algunas propiedades básicas de una red compleja, como las que hemos definido en el apartado anterior, es el primer paso para comprender su estructura. El siguiente paso es, entonces, desarrollar un modelo matemático de la red que proporcione una topología con propiedades estadísticas similares a las reales, obteniendo una plataforma en la que sea posible aplicar diversos métodos matemáticos para analizar comportamientos generales de redes similares.

Redes regulares

Intuitivamente, una red completa tiene la menor longitud de camino promedio (\(L = 1\)ya que todos los nodos están conectados) y el mayor coeficiente de clustering (\(C= 1\)). Aunque el modelo de red completa captura las propiedades de mundo pequeño y alto clustering de muchas redes reales, es fácil darse cuenta de sus limitaciones: una red completa con \(N\) nodos tiene \(N (N-1) / 2\) enlaces, mientras que la mayoría de las redes reales de gran escala parecen tener un número de enlaces de orden \(O(N)\) en lugar de \(O(N^2)\).

De forma menos extrema, podemos considerar las redes regulares de grado k, que son aquellas en las que todos los nodos tienen el mismo grado, que tienen una cantidad lineal de enlaces si \(k<<N\), un alto coeficiente de clustering, y una longitud promedio alta.

Redes aleatorias

En el extremo opuesto del espectro de una red totalmente regular están las redes completamente aleatorias, que como notamos al principio de este texto, fueron estudiadas por Erdös y Rényi (ER) a finales de las década de los 50.
Supongamos que tenemos un gran número de nodos (\(N >> 1\)) y que con una cierta probabilidad \(p\) (la misma siempre), se conecta cada par de nodos con un enlace. El resultado es un grafo aleatorio ER con \(N\) nodos y aproximadamente \(pN (N -1) / 2\) enlaces.

El objetivo principal de la teoría de redes aleatorias es determinar para qué valores de \(p\) aparecerán propiedades específicas en la red. Un resultado sorprendente que se obtuvo fue que algunas de las propiedades importantes podían aparecer de repente, es decir, que si poco a poco modificábamos el valor de \(p\) las redes obtenidas verificaban esa propiedad, y de repente, para un intervalo muy pequeño de variación el comportamiento de las redes obtenidas era completamente distinto... es lo que se conoce como una transición de fase, en donde el cambio de la propiedad medida no es lineal en el cambio del parámetro.

Por ejemplo, una propiedad de este tipo es la de la conectividad global, que se puede medir por medio del tamaño de la componente conexa más grande (la componente gigante): ER mostraron que si la probabilidad \(p\) es superior a un determinado umbral, \(pc \sim (ln N) / N\), prácticamente todo el grafo está conectado (se puede llegar de un nodo a otro por medio de los enlaces), y por debajo de dicho umbral la conectividad era sensiblemente inferior (casi desconectado), en contra de la intuición que parece decirnos que a medida que incrementamos la probabilidad de conexión, \(p\), aumenta proporcionalmente la conectividad global de la red.

El grado medio de una red aleatoria es \(\bar{k} = p (n -1) \sim pN\), y la longitud del camino promedio es \(L \sim ln(N) /\bar{k}\), por lo que, debido a que \(ln N\) crece lentamente en función de \(N\), la longitud del camino promedio se mantiene bastante bajo incluso en una red con muchos nodos. Este aumento logarítmico de la longitud del camino promedio con el tamaño de la red es un efecto típico de mundo pequeño. Por otro lado, en una red aleatoria el coeficiente de clustering es \(C = p = \bar{k} / N << 1\), lo que significa que si tiene muchos nodos apenas mostrará clusterización. De hecho, como ya vimos en el apartado anterior, para un valor de \(N\) muy grande, las redes aleatoria ER son redes casi homogéneas, donde la conectividad sigue aproximadamente una distribución de Poisson.

Redes de Mundo Pequeño

Como hemos comentado, las redes regulares tienen el efecto de clusterización, pero no el de mundo pequeño en general. Por otro lado, los grafos aleatorios muestran el efecto de mundo pequeño, pero no el de clusterización. Por tanto, no debe sorprendernos ver que estos modelos no reproducen algunas características importantes de muchas redes reales. Después de todo, la mayoría de las redes del mundo real no son ni enteramente regulares ni totalmente aleatorias.

Con el fin de describir la transición de una red regular en una aleatoria y disponer de un modelo que mezcle las propiedades deseadas que tienen ambos modelos, Watts y Strogatz introdujeron un interesante modelo de red de mundo pequeño. Las redes del modelo WS pueden ser generadas siguiendo el siguiente algoritmo:

1. Se comienza por una red regular de \(N\) nodos.
2. Se selecciona cada enlace al azar con probabilidad \(p\) y se reconecta uno de sus extremos con cualquiera de los otros nodos de la red.

Este proceso introduce \(pNK / 2\) enlaces de largo alcance que conectan nodos que de otra forma estarían en diferentes vecindarios. Tanto el comportamiento del coeficiente de clustering \(C(p)\) como de la longitud del camino promedio, \(L(p)\), pueden considerarse como una función de la probabilidad de reconexión, \(p\).

Partiendo de un reticulo regular en forma de anillo, sabemos que \(C(0) \sim 3/4\), pero \(L(0)\sim N / 2K >> 1\). Se ha comprobado que para una pequeña probabilidad de reconexión, cuando las propiedades locales de la red son todavía casi las mismas que las de la red regular original, el coeficiente de cluesterización no difiere excesivamete, es decir, que \(C(p) \sim C(0)\), pero que la longitud del camino promedio cae rápidamente y está en el mismo orden que el de las redes aleatorias, es decir, \(L(p) >> L(0)\). Este resultado es bastante natural: por una parte, basta hacer varias reconexiones aleatorias para disminuir la longitud del camino promedio significativamente, pero por otra parte, unas pocas reconexiones no pueden cambiar de manera crucial el valor de clusterización local de la red.

Este modelo de mundo pequeño WS también se puede ver como una red homogénea en la que todos los nodos tienen aproximadamente el mismo número de enlaces. En este sentido, es similar al modelo aleatorio ER. Se han realizado algunas variantes sobre la misma idea, una de ellas fue la propuesta por Newman y Watts, en la que no se rompen conexiones, sino que solo se añaden conexiones entre nodos lejanos con probabilidad \(p\). Si \(p = 0\), tenemos la red original, y si \(p = 1\) se convierte en una red completa. El modelo NW es algo más fácil de analizar que el modelo de WS original, ya que no produce grupos aislados al mantener los enlaces originales. Para valores de \(p\) suficientemente pequeños y \(N\) suficientemente grandes, el modelo NW es esencialmente equivalente al modelo de WS. En la actualidad, estos dos modelos se denominan comunmente modelos de mundo pequeño.

Los modelos de mundo pequeño, tienen sus raíces en las redes sociales no virtuales, donde la mayoría de la gente es amiga de sus vecinos físicos inmediatos, por ejemplo los vecinos en la misma calle o compañeros en la misma oficina. Por otro lado, muchas personas tienen un par de amigos que están lejos, en la distancia, como amigos de otros países, que están representados por las conexiones de largo alcance creadas por el procedimiento de reconexión que hemos visto.

Modelos libres de escala

Como hemos comentado, una característica común de las redes aleatorias y los modelos de mundo pequeño es que la distribución de grados es homogénea, con un pico en el valor promedio y con un decaimiento exponencial. Sin embargo, se ha comprobado que las redes complejas de gran tamaño son libres de escala y sus distribuciones de grado siguen una ley de potencias.

Para explicar el posible origen de esta distribución de grados Barabási y Albert (BA) propusieron otro modelo argumentando que muchos modelos actuales no tienen en cuenta dos atributos importantes de la mayoría de las redes reales:

• Las redes reales son abiertas y tienen una dinámica que añade continuamente nuevos nodos a la red, pero los otros modelos son estáticos en el sentido de que, si bien los enlaces se pueden añadir o reordenar, el número de nodos es constante durante todo el proceso de formación.
• Tanto las redes aleatorias como los modelos de mundo pequeño suponen probabilidades uniformes en el momento de la creación de nuevos enlaces, algo que no es realista. Intuitivamente, las páginas web que ya tienen muchos enlaces (como la página de inicio de Google) tienen más probabilidad de adquirir aún más enlaces; un nuevo artículo es más propenso a citar un artículo ya reconocido, y por tanto éste será mucho más citado que otros menos reconocidos.

El modelo BA sugiere que dos ingredientes principales de la auto-organización de una red en una estructura libre de escala son el crecimiento y el enlace preferencial. El esquema de generación de un modelo libre de escala por BA es el siguiente:

1. Crecimiento: comenzarmos con un número pequeño (\(m_0\)) de nodos; en cada unidad de tiempo, se introduce un nuevo nodo y se conecta a \(m \leq m_0\) de los nodos ya existentes.
2. Enlace preferencial: La probabilidad, \(\Pi_i\), de que un nuevo nodo se conecte al nodo \(i\) (uno de los nodos ya existentes) depende del grado, \(k_i\), de éste: \(\Pi_i = k_i /\sum_j k_j\).

Tras \(t\) pasos, el algoritmo da como resultado una red con \(N = t + m_0\) nodos y \(mt\) enlaces, y se obtiene una red libre de escala: la forma de la distribución de grados no cambia con el tiempo, es decir, no cambia debido a un aumento de la escala de la red. La distribución de grados sigue una ley de potencias con exponente -3, es decir, la probabilidad de encontrar un nodo con \(k\) enlaces es proporcional a \(k^{-3}\).

Los resultados numéricos muestran que, en comparación con una red aleatoria con el mismo número de nodos y el mismo grado medio, la longitud del camino promedio del modelo libre de escala es algo menor, y sin embargo el coeficiente de clustering es mucho mayor. Esto implica que la existencia de unos pocos nodos con grado alto desempeña un papel clave en acercar los nodos entre sí.

El modelo BA es un modelo minimalista que captura los mecanismos responsables de la distribución de grados que sigue una ley de potencias, aunque tiene algunas limitaciones evidentes cuando se compara con algunas redes del mundo real, lo que ha provocado que se haya intensificado la búsqueda de otros modelos evolutivos que superen estas limitaciones.

Vulnerabilidad de las redes libres de escala

Un fenómeno interesante de las redes complejas libres de escala (y de muchas redes complejas en general) es su robustez frente a fragilidad. Vamos a ilustrarla por medio del siguiente caso:

Vamos a suponer que comenzamos con una red grande y conectada, y que en cada unidad de tiempo eliminamos un nodo al azar (la eliminación del nodo implica la eliminación de todas sus conexiones, lo que altera algunos de los caminos entre los nodos restantes). Si había múltiples caminos entre dos nodos \(i\) y \(j\), la eliminación de uno de los nodos que forma parte de uno de esos caminos puede suponer que la distancia entre ellos, \(d_{ij}\), se incrementará, lo que, a su vez, puede causar el aumento de la longitud del camino promedio de toda la red. En el peor de los casos, si inicialmente había un solo camino entre esos dos nodos, la interrupción de este camino en particular significaría que los dos nodos quedarían desconectados (pudiendo pasar de una red conexa a una formada por islas desconectadas entre sí).

Se considera que la conectividad de una red es robusta (o tolerante a borrados) si tras la eliminación de muchos de sus nodos sigue conteniendo una componente conexa gigante. Las redes libres de escala verifican esta propiedad, mostrándose robustas frente a eliminaciones aleatorias.

Sin embargo, la mala noticia es que la mayoría de las redes libres de escala son muy sensibles a eliminaciones dirigidas, no aleatorias, basta eliminar una proporción muy baja de nodos específicos (por ejemplo, aquellos de grado alto, los concentradores) para que la red quede completamente dividida y muy dispersa. Este último hecho indica que la red es muy frágil. Esta fragilidad tiene sus raíz en la naturaleza extremadamente no homogénea de la distribución de grados de las redes libres de escala.