Modelo de mundo pequeño: uso de Python Networkx

En este artículo, aprenderemos cómo crear una red Small World utilizando el módulo Networx en Python. Antes de continuar, primero comprendamos algunos conceptos básicos sobre Small World Phenomenon.

¿Qué es el fenómeno del mundo pequeño ?
Small World Phenomenon es el estudio y la noción de que todos estamos conectados a través de un pequeño número de bordes. Ha habido tres experimentos notables para probar el Fenómeno del Mundo Pequeño:

1. Experimento Milgram Small World Phenomenon: se pidió a 296 personas elegidas al azar que enviaran una carta a una persona ‘objetivo’ (un corredor de bolsa en Boston). La carta debía enviarse directamente a él si la persona era conocida personalmente, de lo contrario, la carta debía enviarse a alguien que tenga una mayor probabilidad de conocerlo personalmente. 64 letras llegaron a la persona objetivo con una longitud media de 6, es decir. en promedio, una persona aleatoria se conectaba con la persona objetivo a través de 6 personas en el medio.
2. Experimento de Miscrosoft Instant Messenger: Hay 240 millones de usuarios activos de Microsoft Instant Messenger. Están conectados si dos usuarios participaron en una comunicación bidireccional durante el período de un mes. Para dos personas aleatorias cualesquiera, la distancia media fue de 7, es decir, 2 personas aleatorias estaban conectadas a través de 7 conexiones intermedias.
3. Experimento basado en Facebook: el experimento realizado por Facebook calculó que la longitud de ruta promedio era 5,28 en 2008, mientras que se redujo a 4,74 en 2011.

En 1998, Duncan Watts y Steven Strogatz avanzaron en el estudio de Small World Model al publicar un artículo de investigación titulado «Dinámica colectiva de las redes de Small World». Estudiaron tres tipos diferentes de redes:

1. Una red de actores de cine , donde los Nodes individuales eran actores de cine y estaban conectados solo si los actores aparecían en la misma película.
2. Una red de red eléctrica donde los Nodes son generadores, transformadores y subestaciones y dos Nodes están vinculados si tienen una línea de transmisión entre ellos.
3. Una red donde los Nodes son neuronas y dos Nodes están vinculados si tienen una sinapsis o una unión gap.

Llegaron a la conclusión de que Small World Networks generalmente tiene una longitud de ruta promedio baja pero un coeficiente de agrupamiento alto.
 

¿Cómo se pueden formar las Redes de Pequeños Mundos?

Watts y Strogatz propusieron un modelo sobre cómo construir Small World Networks. Deje que haya n Nodes, donde cada Node está conectado a m vecinos más cercanos, esto se conoce como celosía regular y se ve como se muestra en la figura a continuación, donde n = 10 y m = 4.

Considere cada borde (u, v) y con probabilidad p , seleccione un Node w al azar y vuelva a cablear el borde (u, v) para que se convierta en (u, w) . Para p = 0 , el Enrejado Regular conserva su estructura y tiene una distancia promedio alta y un agrupamiento alto. Para p = 1 , se forma una red aleatoria con una distancia media pequeña y un agrupamiento bajo. Se parece a la figura que se muestra a continuación, donde n = 10, m = 4 y p = 1.

Para un valor intermedio de p , obtendríamos una Small World Network ideal con una distancia promedio pequeña y un agrupamiento alto.

Para Python, podemos construir fácilmente una Small World Network usando Networkx.

import networkx as nx
import matplotlib.pyplot as plt
  
G = nx.watts_strogatz_graph(n = 10, m = 4, p = 0.5)
pos = nx.circular_layout()
  
plt.figure(figsize = (12, 12))
nx.draw_networkx(G, pos)

Producción:

La Small World Network resultante puede ser un gráfico desconectado. Si deseamos obtener un gráfico conectado, podemos modificar la línea número 4 del código anterior de la siguiente manera:

G = nx.connected_watts_strogatz_graph(n=10, m=4, p=0.5, t=20)

Ejecuta la función original t veces (en este caso t = 20) hasta que se logra una red conectada. Dará la siguiente red:

G = nx.newman_watts_strogatz_graph(n=10, m=4, p=0.5)

El código anterior ejecutará un modelo similar pero agregará nuevos bordes con probabilidad p en lugar de volver a cablear los bordes ya existentes. Producirá la siguiente red: