16.3: Simulación de dinámicas de redes

Los modelos de dinámica de redes capturan tipos completamente diferentes de dinámicas de red, es decir, cambios en las topologías de red. Esto incluye la adición y eliminación de nodos y bordes a lo largo del tiempo. Como se discutió en el capítulo anterior, tales cambios dinámicos de la topología del sistema en sí son bastante inusuales desde el punto de vista de los sistemas dinámicos tradicionales, porque harían imposible asumir un espacio de fase estático bien definido del sistema. Pero permitir tales cambios topológicos abre un conjunto completamente nuevo de posibilidades para modelar diversos fenómenos naturales y sociales que eran difíciles de capturar en los marcos de los sistemas dinámicos convencionales, tales como:

• Cambios evolutivos de las redes reguladoras y metabólicas génicas
• Autoorganización y adaptación de las redes alimentarias
• Formación y evolución de redes sociales
• Crecimiento de las redes de infraestructura (por ejemplo, redes de tráfico, redes eléctricas, Internet, WWW)
• Crecimiento de las redes de citas científicas

Como se vio anteriormente, el crecimiento y la evolución de las redes en la sociedad están particularmente bien estudiados utilizando dinámicas de modelos de redes. Esto se debe en parte a que sus cambios temporales tienen lugar mucho más rápido que otras redes naturales que cambian a escalas de tiempo ecológico/evolutivo, y así los investigadores pueden compilar una gran cantidad de datos de redes temporales con relativa facilidad.

Un problema icónico que se ha discutido sobre las redes sociales es este: ¿Por qué nuestro mundo es tan “pequeño” a pesar de que hay millones de personas en él? Esto fue llamado el problema del “mundo pequeño” por el psicólogo social Stanley Milgram, quien lo demostró experimentalmente a través de su famoso experimento de “seis grados de separación” en la década de 1960 [71]. Este hecho empírico, de que cualquier par de individuos humanos en nuestra sociedad es probable que esté conectado a través de un camino hecho solo de un pequeño número de socialtades, ha estado desconcertando a mucha gente, entre ellos investigadores. Este problema no suena trivial, porque normalmente solo tenemos la información sobre las conexiones sociales locales a nuestro alrededor, sin saber mucho sobre cómo cada uno de nuestros conocidos está conectado con el resto del mundo. Pero probablemente sea cierto que usted está conectado con, digamos, el Presidente de Estados Unidos por menos de diez vínculos sociales.

Este problema del pequeño mundo ya tenía una explicación matemática clásica. Si la red es puramente aleatoria, entonces la distancia promedio entre pares de nodos es extremadamente pequeña. En este sentido, los modelos de gráficos aleatorios Erdős—Rényi ya pudieron explicar maravillosamente el problema del mundo pequeño. Sin embargo, hay un problema con esta explicación: ¿Cómo es que una persona que solo tiene información local puede conectarse con individuos elegidos al azar de toda la sociedad, que podrían estar viviendo en el lado opuesto del globo? Esta es una preocupación legítima porque, después de todo, la mayoría de nuestras conexiones sociales están dentro de un círculo cercano de personas que nos rodean. La mayoría de las conexiones sociales son muy locales tanto en el sentido geográfico como en el social, y no hay forma de que podamos crear una red verdaderamente aleatoria en el mundo real. Por lo tanto, necesitamos diferentes tipos de mecanismos mediante los cuales las redes sociales cambien sus topologías para adquirir la propiedad del “pequeño mundo”.

A continuación, discutiremos dos dinámicas de modelos de redes que pueden explicar muy bien el problema del pequeño mundo en escenarios más realistas. Curiosamente, estos modelos se publicaron aproximadamente al mismo tiempo, a fines de la década de 1990, y ambos contribuyeron en gran medida al establecimiento del nuevo campo de la ciencia de redes.

Redes de mundo pequeño mediante recableado aleatorio de bordes

En 1998, Duncan Watts y Steven Strogatz abordaron esta paradoja, que las redes sociales son “pequeñas” pero altamente agrupadas localmente, al introducir el modelo de red de mundo pequeño [56]. El modelo Watts-Strogatz se basa en un procedimiento de recableado aleatorio de bordes para modificar gradualmente la topología de red de una topología completamente regular, local, agrupada a una completamente aleatoria, global y no agrupada. En medio de este proceso de recableado aleatorio, encontraron redes que tenían la propiedad de “mundo pequeño” pero que aún mantenían topologías agrupadas localmente. Llamaron a estas redes redes de “mundo pequeño”. Tenga en cuenta que tener la propiedad de “mundo pequeño” no es una condición suficiente para que una red se llame “mundo pequeño” en el sentido de Watts-Strogatz. La red también debe tener un alto agrupamiento local.

Watts y Strogatz no propusieron su procedimiento de recableado de bordes aleatorios como un proceso dinámico a lo largo del tiempo, pero aún podemos simularlo como un modelo de dinámica en redes. Aquí están sus suposiciones modelo originales:

1. La topología de red inicial es una red en forma de anillo compuesta por n nodos. Cada nodo está conectado a los vecinos\(k\) más cercanos (es decir, los vecinos\(k/2\) más cercanos en el sentido de las agujas del reloj y los vecinos\(k/2\) más cercanos en el sentido contrario
2. Cada borde está sujeto a recableado aleatorio con probabilidad\(p\). Si se selecciona para recableado aleatorio, uno de los dos extremos del borde se vuelve a conectar a un nodo que se elige aleatoriamente de toda la red. Si este recableado causa bordes duplicados, el recableado se cancela.

El modelo original de Watts y Strogatz realizó el recableado aleatorio de bordes (paso 2 anterior) visitando secuencialmente cada nodo en sentido horario. Pero aquí, podemos hacer una pequeña revisión al modelo para que el recableado de borde represente un evento social más realista, como un encuentro aleatorio en el aeropuerto de dos individuos que viven lejos el uno del otro, etc. Aquí están los nuevos supuestos del modelo revisados:

1. La topología de red inicial es la misma que la descrita anteriormente.
2. En cada evento de recableado de bordes, se selecciona aleatoriamente un nodo de toda la red. El nodo cae uno de sus bordes aleatoriamente, y luego crea un nuevo borde a un nuevo nodo que se elige aleatoriamente de toda la red (excluyendo aquellos a los que el nodo ya está conectado).

Este modelo captura esencialmente el mismo procedimiento que Watts y Strogatz, pero la probabilidad de recableado ahora\(p\) está representada implícitamente por la duración de la simulación. Si la simulación continúa indefinidamente, entonces la red eventualmente se volverá completamente aleatoria. Tal proceso dinámico puede interpretarse como un modelo de evolución social en el que una sociedad inicialmente agrupada localmente acumula gradualmente cada vez más conexiones globales que son causadas por encuentros raros y aleatorios de largo alcance entre las personas.

Simulemos este modelo usando Python. Cuando se simula la dinámica de las redes, un reto práctico es cómo visualizar los cambios topológicos de la red. A diferencia de los estados de nodo que se pueden visualizar fácilmente usando colores, la topología de red es la forma de la propia red, y si la forma de la red está cambiando dinámicamente, también necesitamos simular el movimiento físico de los nodos en el espacio de visualización también. Esto es solo para visualización estética, que no tiene nada que ver con la ciencia real que está pasando en la red. Pero una visualización efectiva a menudo nos ayuda a entender mejor lo que está pasando en la simulación, así que probemos un poco de animación elegante aquí. Afortunadamente, la función spring_layout de NetworkX se puede utilizar para actualizar ligeramente las posiciones actuales de los nodos. Por ejemplo:

Este código calcula un nuevo conjunto de posiciones de nodo usando g.pos como posiciones iniciales y aplicándoles el algoritmo dirigido a la fuerza Fruchterman-Reingold por solo cinco pasos. Esto simulará efectivamente un ligero movimiento de los nodos desde sus posiciones actuales, lo que puede ser utilizado para animar los cambios topológicos sin problemas.

Aquí hay un ejemplo del código de simulación completado para la formación de redes de mundo pequeño mediante recableado aleatorio de bordes:

La función de inicialización crea una topología de red en forma de anillo conectando cada nodo a sus k vecinos más cercanos (\(j ∈ {1,...,k/2}\)). “% n” se utiliza para confinar los nombres de los nodos al dominio\([0,n−1]\) con condiciones de límite periódicas. También se crea un atributo g.count adicional para contar los pasos de tiempo entre eventos de cambios topológicos. En la función de actualización, g.count se incrementa en uno, y el recableado de borde aleatorio se simula en cada 20 pasos de la siguiente manera: Primero, se elige aleatoriamente el nodo i, y luego se elimina una de sus conexiones. Entonces el propio nodo i y sus vecinos se eliminan de la lista de nodos candidatos. Luego se crea un nuevo borde entre i y un nodo elegido aleatoriamente de los nodos candidatos restantes. Finalmente, independientemente de si se produjo o no un recableado de borde aleatorio, el movimiento del nodo se simula usando la función spring_layout.

Ejecutar este código te dará un proceso animado de recableado aleatorio de bordes, que gradualmente convierte una red regular, local, agrupada en una red aleatoria, global y no agrupada (Fig. 16.3.1). En algún lugar de esta dinámica de red, verá surgir la red de Watts-Strogatz smallworld, pero solo temporalmente (que se discutirá más adelante en el próximo capítulo) .N

Figura\(\PageIndex{1}\): Salida visual de Código 16.10. El tiempo fluye de izquierda a derecha.

Ejercicio\(\PageIndex{1}\)

Revisar el modelo de formación de redes de mundo pequeño anterior para que la red se encuentre inicialmente en una cuadrícula bidimensional en la que cada nodo esté conectado a sus cuatro vecinos (norte, sur, este y oeste; excepto aquellos en los límites del espacio). Luego ejecute las simulaciones y vea cómo el recableado aleatorio de bordes cambia la topología de la red.

Para su información, NetworkX ya cuenta con una función de generación de gráficos incorporada para redes de mundo pequeño Watts-Strogatz, watts_strogatz_graph (n, k, p). Aquí, n es el número de nodos, k es el grado de cada nodo y p es la probabilidad de recableado de bordes. Si no necesitas simular la formación de redes de mundo pequeño iterativamente, solo debes usar esta función en su lugar.

Redes libres de escala por conexión preferencial

El modelo de red de mundo pequeño de Watts-Strogatz produjo un gran avance en la explicación de las propiedades de las redes del mundo real utilizando modelos de red abstractos. Pero claro, no estaba libre de limitaciones. Primero, su modelo requirió una probabilidad de recableado de “Ricitos de Oro”\(p\) (o tal longitud de simulación en nuestro modelo revisado) para obtener una red de mundo pequeño. Esto quiere decir que su modelo no pudo explicar cómo se\(p\) mantendría tal apropiado en las redes sociales reales. Segundo, las redes de pequeño mundo generadas por su modelo no capturaron un aspecto importante de las redes del mundo real: la heterogeneidad de las conectividades. En todos los niveles de la sociedad, a menudo encontramos algunas personas muy populares, así como muchas otras personas menos populares, “comunes”. En otras palabras, siempre hay una gran variación en los grados de nodo. Sin embargo, dado que el modelo Watts-Strogatz modifica una gráfica inicialmente regular mediante una serie de recableados aleatorios, las redes resultantes siguen siendo bastante cercanas a lo regular, donde cada nodo tiene más o menos el mismo número de conexiones. Esto es bastante diferente a lo que solemos ver en la realidad.

Apenas un año después de la publicación del artículo de Watts y Strogatz, Albert-l'Aszl'o Barab'asi y R'eka Albert publicaron otro artículo muy influyente [57] sobre un nuevo modelo que podría explicar tanto la propiedad del mundo pequeño como grandes variaciones de grados de nodo en una red. El modelo Barab'asi-Albert describió la autoorganización de las redes a lo largo del tiempo causada por una serie de eventos de crecimiento de redes con apego preferencial. Sus supuestos modelo fueron los siguientes:

1. La topología de red inicial es un gráfico arbitrario hecho de\(m_0\) nodos. No existe un requisito específico para su forma, siempre y cuando cada nodo tenga al menos una conexión (por lo que su grado es positivo).
2. En cada evento de crecimiento de red, un nodo recién llegado se une a la red por\(m\) bordes\((m ≤ m_0)\). El destino de cada borde se selecciona de la red de nodos existentes utilizando las siguientes probabilidades de selección:

\[p(i)= \frac{\deg{(1)}}{\sum{\deg(j)}_{j}} \label{(16.16)} \]

Este mecanismo de apego preferencial captura el efecto de “los ricos se hacen más ricos” en el crecimiento de los sistemas, lo que a menudo se ve en muchos procesos socioeconómicos, ecológicos y físicos. Dicha ventaja acumulativa también se llama el “efecto Mateo” en sociología. Lo que encontraron Barab'asi y Albert fue que la red que crece con esta simple regla dinámica eventualmente formará un cierto tipo de topología en la que la distribución de los grados de nodo sigue una ley de poder

\[P(k) \approx{k}^{-\gamma}, \label{(16.17)} \]

donde\(P(k)\) es la probabilidad de que un nodo tenga grado\(k\), y\(−γ \) es el exponente de escalado (\(γ = 3\)en el modelo Barab'asi-Albert). Dado que el exponente es negativo, esta distribución significa que la mayoría de los nodos tienen muy pequeños\(k\), mientras que solo unos pocos nodos tienen grandes\(k\) (Fig. 16.10). Pero la implicación clave es que esos nodos “hub” súper populares sí existen en esta distribución, lo que no sería posible si la distribución fuera una distribución normal, por ejemplo. Esto se debe a que una distribución de ley de poder tiene una cola larga (también llamada cola gorda, cola pesada, etc.), en la que la probabilidad baja mucho más lentamente que en la cola de una distribución normal a medida que\(k\) se hace más grande. Barab'asi y Albert llamaron redes cuyas distribuciones de grado siguen una ley de poder redes libres de escala, porque no hay una “escala” característica que destaque en sus distribuciones de grado.

Figura:Parcelas\(\PageIndex{2}\) de la distribución de la ley de poder con\(P(k) ∼ k^{γ}\).\(γ = 3\) Izquierda: En escalas lineales. Derecha: En escalas log-log.

El crecimiento de la red con adjuntos preferenciales es un proceso interesante y divertido de simular. También podemos reutilizar la mayor parte del Código 16.10 para este propósito. Un componente crítico que necesitaremos definir de nuevo es la función de selección de nodo preferencial que elige aleatoriamente un nodo en función de los grados de nodo. Esto se puede lograr mediante la selección de ruleta, es decir, crear una “ruleta” a partir de los grados de nodo y luego decidir en qué bin de la ruleta cae un número generado aleatoriamente. En Python, esta función de selección de nodo preferencial se puede escribir de la siguiente manera:

Figura\(\PageIndex{3}\): Ilustración esquemática de la selección de ruleta implementada en el Código 16.11.

Con esta función de selección de nodo preferencial, el código de simulación completado se ve así:

En este código de muestra, el crecimiento de la red comienza con una gráfica completa de cinco nodos. Cada vez que se agrega un nodo recién llegado a la red, se establecen dos nuevos bordes. Tenga en cuenta que cada vez que se crea un borde entre el recién llegado y un nodo j existente, el nodo j se elimina de la lista de candidatos nds para que no se creen bordes duplicados. Por último, se agrega una nueva posición (0, 0) para el recién llegado a g.pos. Dado que g.pos es un diccionario Python, se puede insertar una nueva entrada simplemente usando newcomer como clave.

La Figura 16.12 muestra un resultado típico de simulación en el que se ven espontáneamente nodos concentradores altamente conectados. Cuando continúas con esta simulación el tiempo suficiente, la distribución resultante de grados de nodo se acerca a una distribución de ley de potencia con γ = 3.

\(\PageIndex{4}\)Figura:Salida visual de Código 16.12. El tiempo fluye de izquierda a derecha.

Ejercicio\(\PageIndex{2}\)

Simule el modelo de crecimiento de la red Barab'asi-Albert con\(m = 1\)\(m = 3\)\(m = 5\), y, y vea cómo el proceso de crecimiento puede verse afectado por la variación de este parámetro.

Ejercicio\(\PageIndex{3}\)

Modifique la función de selección de nodo preferencial para que la probabilidad de selección de nodos\(p(i)\) sea cada una de las siguientes:

• independiente del grado del nodo (conexión aleatoria)
• proporcional al cuadrado del grado del nodo (fuerte apego preferencial)
• inversamente proporcional al grado del nodo (apego preferencial negativo) Realizar simulaciones para estos casos y comparar las topologías de red resultantes.

Tenga en cuenta que NetworkX también tiene una función de generación de gráficos incorporada para las redes libres de escala Barab'asi-Albert, llamada barabasi_albert_graph (n, m). Aquí, n es el número de nodos, y m el número de bordes por los cuales cada nodo recién llegado está conectado a la red.

Aquí hay algunos ejercicios más de dinámica de modelos de redes, para su posterior exploración:

Ejercicio\(\PageIndex{4}\): Closing triangles

Este ejemplo es una versión algo invertida del modelo de red de mundo pequeño de Watts-Strogatz. En lugar de hacer una red local agrupada en una red global y no agrupada, podemos considerar un proceso dinámico que haga que una red no agrupada sea más agrupada con el tiempo. Aquí están las reglas:

• La red es inicialmente aleatoria, por ejemplo, una gráfica aleatoria Erd"os-R'enyi.
• En cada iteración, se selecciona aleatoriamente una ruta de dos bordes (A-B-C) de la red.
• Si no hay borde entre A y C, uno de ellos pierde uno de sus bordes (pero no el que conecta con B), y A y C están conectados entre sí en su lugar.

Se trata de un proceso de recableado de bordes que cierra un triángulo entre A, B y C, promoviendo lo que se llama un cierre triádico en sociología. Implemente este modelo de recableado de bordes, realice simulaciones y vea qué tipo de topología de red resulta de esta regla de cierre triádica. También puede combinar esta regla con el recableado aleatorio de bordes utilizado en el modelo Watts-Strogatz, para explorar diversos equilibrios entre estas dos reglas en competencia (globalización y localización) que dan forma a la autoorganización de la topología de red.

Ejercicio\(\PageIndex{5}\): Preferential attachment with node division

Podemos considerar una modificación del modelo Barab'asi-Albert donde cada nodo tiene un límite de capacidad en términos del número de conexiones que puede contener. Supongamos que si el grado de un nodo excede su capacidad predefinida, el nodo se divide en dos, y cada nodo hereda aproximadamente la mitad de las conexiones que tenía el nodo original. Este tipo de división de nodos puede considerarse una representación de una división de una empresa u organización, o la evolución de diferentes genes especializados a partir de un solo gen que tenía muchas funciones. Implemente este modelo de crecimiento de red modificado, realice simulaciones y vea cómo la división de nodos influye en la topología de red resultante.