Modelo de Watts-Strogatz

El modelo de Watts-Strogatz es un modelo de generación aleatoria de grafos que produce grafos con propiedades de mundo pequeño , incluyendo longitudes de camino promedio cortas y alta agrupación . Fue propuesto por Duncan J. Watts y Steven Strogatz en su artículo publicado en 1998 en la revista científica Nature . ^{[ 1 ]} El modelo también se conoció como el modelo beta (de Watts) después de que Watts utilizara${\displaystyle \beta }$para formularlo en su libro de divulgación científica Six Degrees .

El estudio formal de los grafos aleatorios se remonta al trabajo de Paul Erdős y Alfréd Rényi . ^{[ 2 ]} Los grafos que consideraron, ahora conocidos como los grafos clásicos o de Erdős-Rényi (ER) , ofrecen un modelo simple y potente con muchas aplicaciones.

Sin embargo, los grafos ER no poseen dos propiedades importantes que se observan en muchas redes del mundo real:

1. No generan agrupamiento local ni cierres triádicos . En cambio, debido a que tienen una probabilidad constante, aleatoria e independiente de que dos nodos estén conectados, los grafos ER tienen un coeficiente de agrupamiento bajo .
2. No tienen en cuenta la formación de nodos centrales. Formalmente, la distribución de grados de los grafos ER converge a una distribución de Poisson , en lugar de una ley de potencias observada en muchas redes libres de escala del mundo real . ^{[ 3 ]}

El modelo de Watts y Strogatz se diseñó como el modelo más simple posible que aborda la primera de las dos limitaciones. Considera la agrupación manteniendo las cortas longitudes de camino promedio del modelo ER. Lo hace interpolando entre una estructura aleatoria cercana a los grafos ER y una red de anillos regular . En consecuencia, el modelo puede explicar, al menos parcialmente, el fenómeno de "mundo pequeño" en diversas redes, como la red eléctrica, la red neuronal de C. elegans , las redes de actores de cine o la comunicación del metabolismo de las grasas en la levadura en gemación . ^{[ 4 ]}

Dado el número deseado de nodos${\displaystyle N}$, el grado medio${\displaystyle K}$(se supone que es un número entero par) y un parámetro${\displaystyle \beta }$, todo satisfactorio${\displaystyle 0\leq \beta \leq 1}$y${\displaystyle N\gg K\gg \ln N\gg 1}$, el modelo construye un grafo no dirigido con${\displaystyle N}$nodos y${\displaystyle {\frac {NK}{2}}}$bordes de la siguiente manera:

1. Construir una red de anillos regular, un grafo con${\displaystyle N}$nodos cada uno conectado a${\displaystyle K}$vecinos,${\displaystyle K/2}$en cada lado. Es decir, si los nodos están etiquetados ${\displaystyle 0\ldots {N-1},}$hay un borde${\displaystyle (i,j)}$si y solo si${\displaystyle 0<|ij|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}$
2. Para cada nodo${\displaystyle i=0,\dots ,{N-1}}$aprovechar cada borde que conecta${\displaystyle i}$a su${\displaystyle K/2}$vecinos más a la derecha, es decir, cada borde.${\displaystyle (i,j)}$de tal manera que${\displaystyle 0<(ji)\ \mathrm {mod} \ N\leq K/2}$y volver a cablearlo con probabilidad${\displaystyle \beta }$El recableado se realiza reemplazando${\displaystyle (i,j)}$con${\displaystyle (i,k)}$dónde${\displaystyle k}$se elige uniformemente al azar de entre todos los nodos posibles evitando bucles propios (${\displaystyle k\neq i}$) y duplicación de enlaces (no hay borde)${\displaystyle (i,{k'})}$con${\displaystyle k'=k}$en este punto del algoritmo).

La estructura reticular subyacente del modelo produce una red agrupada localmente, mientras que los enlaces reconectados aleatoriamente reducen drásticamente las longitudes promedio de los caminos . El algoritmo introduce aproximadamente${\displaystyle \beta {\frac {NK}{2}}}$de tales bordes no reticulares. Variante${\displaystyle \beta }$permite interpolar entre una red regular (${\displaystyle \beta =0}$) y una estructura cercana a un gráfico aleatorio Erdős-Rényi${\displaystyle G(N,p)}$con${\displaystyle p={\frac {K}{N-1}}}$en${\displaystyle \beta =1}$No se aproxima al modelo ER real ya que cada nodo estará conectado a al menos${\displaystyle K/2}$otros nodos.

Las tres propiedades de interés son la longitud media del camino , el coeficiente de agrupamiento y la distribución de grados .

La principal limitación del modelo es que produce una distribución de grados poco realista . En contraste, las redes reales suelen ser redes libres de escala, heterogéneas en cuanto a su grado, con nodos centrales y una distribución de grados libre de escala. Estas redes se describen mejor en este sentido mediante la familia de modelos de conexión preferencial , como el modelo de Barabási-Albert (BA) . (Por otro lado, el modelo de Barabási-Albert no reproduce los altos niveles de agrupamiento observados en redes reales, una deficiencia que no comparte el modelo de Watts y Strogatz. Por lo tanto, ni el modelo de Watts y Strogatz ni el de Barabási-Albert deben considerarse completamente realistas).

El modelo de Watts y Strogatz también implica un número fijo de nodos y, por lo tanto, no puede utilizarse para modelar el crecimiento de la red.

• Redes de mundo pequeño
• Modelo de Erdős-Rényi (ER)
• Modelo de Barabási-Albert
• Redes sociales