RD2023_DS_C1_SC3_T1_L4_R3

Modelo de Watts-Strogatz (mundo pequeño)

A través de esta lectura interactiva conoce las características de las redes de mundo pequeño.

Comenzar

Modelo de Watts-Strogatz (mundo pequeño)

El modelo de Erdös-Rényi, que estudiamos en el recurso anterior, es útil para generar redes aleatorias. Sin embargo, no siempre refleja las características de las redes que deseamos estudiar, ya que suelen surgir de procesos distintos a la aleatoriedad. Es por ello que el entra el Modelo de Watts-Strogatz, que también utiliza un proceso aleatorio para generar redes, pero con el objetivo de obtener un tipo particular de redes conocidas como “redes de mundo pequeño”.

¿Qué es una red de mundo pequeño?

Se les llama redes de mundo pequeño a aquellas en las que los nodos pueden estar conectados por caminos relativamente cortos, pocos enlaces o saltos. ¿Has escuchado sobre los “seis grados de separación”?

1/10

Uno de los experimentos más famosos para comprobar esta teoría fue llevado a cabo por el psicólogo social Stanley Milgram. Seleccionó a 160 personas de manera aleatoria en Omaha, Nebraska, para que enviaran un paquete a una persona específica en Boston, Massachusetts. Este envío se tenía que hacer únicamente a través de personas conocidas. El resultado mostró que las cadenas de envíos variaban de 2 a 10 intermediarios, con un promedio de 6.

2/10

Ejemplo del experimento social de Stanley Milgram

Persona de gobierno

Profesor

Presidente

Gobier-no

Profe-sor

Profe-sor

Presi-dente

Tú

3/10

Si se pueden establecer estas dos conexiones, tú estarías a solo tres "saltos" de distancia del presidente de Estados Unidos. ¿Es fascinante, verdad? Este es solo un ejemplo, es importante tener en cuenta que esta es solo una aproximación y que, en la realidad, las conexiones entre personas pueden ser mucho más complejas y variadas. Con el ejemplo anterior puedes darte cuenta de que las redes de mundo pequeño son fascinantes porque se encuentran en muchas situaciones del mundo real. Se puede ver la facilidad de la propagación de la información y conexión entre personas distintas.

4/10

Distancia promedio del modelo G(n,p)

Dentro del marco del modelo G(n,p) que exploramos previamente en el recurso anterior, es posible estimar la distancia promedio en una red utilizando la siguiente fórmula:

Donde γ≈0.5772 es la constante de Euler. Esta constante es un número irracional de relevancia en diversas áreas matemáticas. Se incorpora en la fórmula para afinar la estimación de la distancia promedio. Su inclusión toma en consideración las propiedades particulares de la red generada por el modelo G(n,p). Aquí, H representa una red en el modelo G(n,p). Cuando el promedio de los grados de los vértices en la red aumenta, la distancia promedio tiende a disminuir. Esto implica que, mediante este proceso, es posible obtener redes de mundo pequeño. Sin embargo, uno de los problemas es que, en general, estos grafos pueden carecer de otras propiedades deseables. Para abordar esta limitación, surge el modelo de Watts-Strogatz, creado por Duncan J. Watts, profesor de sociología en la Universidad de Pensilvania, y Steven Strogatz, matemático y profesor en la Universidad Cornell.

5/10

Procedimiento para generar redes con el Modelo de Watts-Strogatz

El modelo de Watts-Strogatz se basa en un conjunto de vértices, representados por V={V1, V2, ..., Vn}, donde n es la cantidad total de vértices. También se elige un número par k, que debe cumplir la condición de que n sea mucho mayor que k, y k sea mucho mayor que el logaritmo natural de n, y este último mucho mayor que 1. El proceso para construir la red llamada "anillo en celosía" es el que se muestra a continuación.

Paso 2

Paso 3

Paso 1

El resultado de este proceso es lo que llamamos una "red aleatoria de Watts-Strogatz", que se denota como WS(n,k,p).

6/10

Ejemplo de redes WS(n,k,p)

Esta red WS(n,k,p) comparte propiedades interesantes, como la propiedad de mundo pequeño, lo que la hace especialmente útil para modelar diversas situaciones del mundo real, incluyendo redes sociales y otras redes complejas. Veamos 2 ejemplos de una red de este tipo:

En este ejemplo en particular se refiere a la probabilidad p mencionada en el algoritmo, tiene además 20 vértices y k=4.

Esta es una red Watss-Strogatz de 100 vértices

Una red de Watss-Strogatz nos da una red de mundo pequeño. Como de inicio tenemos una serie de vértices conectados entre sí, tenemos agrupamiento, como tienen las redes sociales en general.

7/10

Distancia promedio en el Modelo de Watts-Strogatz

Ya que repasamos la fórmula de distancia promedio en las redes con el modelo G(n,p) y el procedimiento para obtener una red con el modelo de Watts-Strogatz (anillo de celosía), veamos la propiedad de distancia promedio en los grafos WS(n,k,p). La longitud promedio la llamaremos l(p), ya que depende de la probabilidad p. El anillo de celosía nos da una distancia promedio l(0)=n/2k

ln (n)

ln (k)

• Si p→1 (p tiende a 1), lo que tenemos es un grafo aleatorio y l(1)

• Para 0<β<1 lo que tenemos es que la longitud promedio desciende.

8/10

Por ejemplo, supongamos que tenemos un grafo aleatorio con 10 nodos (n = 10) y cada nodo está conectado a sus 2 vecinos más cercanos en un anillo (k = 2).

Usando la fórmula que mencionamos anteriormente, tenemos:l(0) = n / (2k) = 10 / (2 * 2) = 10 / 4 = 2.5 Esto significa que, en promedio, la distancia entre dos nodos aleatorios en este grafo sería aproximadamente 2.5.

9/10

Modelo de Watts-Strogatz (mundo pequeño)

En el contexto de grafos aleatorios, p suele representar la probabilidad de que dos nodos estén conectados por una arista. Si p tiende a 1, entonces prácticamente todos los pares de nodos estarán conectados por una arista, lo que transforma el grafo en un grafo completo.

Esta figura presenta un grafo aleatorio con 4 nodos, donde la probabilidad "p" es alta y todos los pares de nodos están conectados por aristas.

10/10

¡Muy bien!

En el siguiente recurso veremos otro tipo de red, conocida como redes libres de escala.

Reiniciar

Luego, esa persona en el gobierno de Estados Unidos, a su vez, tiene una conexión cercana con el presidente.

Luego, para cada arista (v,w) que ya existe en el grafo original, elegimos un vértice u al azar de manera uniforme, siempre y cuando u no esté conectado previamente con v. Luego, con una probabilidad p, quitamos la arista (v,w) y la reemplazamos por la arista (v,u).

Para cada vértice v que pertenece a V (recuerda que es el conjunto de nodos o vértices en la red), conectamos v con la mitad de los k vértices que están a su izquierda (en contra del sentido de las manecillas del reloj) y con la otra mitad que están a su derecha (en el sentido de las manecillas del reloj). Esto crea una estructura inicial de conexiones.

Supongamos que conoces a un profesor del ITESM.

Colocamos los vértices en un círculo o anillo, como si estuvieran formando una circunferencia.

Ese docente cuenta con un compañero en una institución académica extranjera que mantiene vínculos políticos o sociales estrechos con un individuo que trabaja en el gobierno de Estados Unidos, ya sea como diplomático o asesor cercano al presidente.