Modelo Watts-Strogatz

El modelo Watts-Strogatz es un modelo de generación de gráficos aleatorios que produce gráficos con propiedades de mundo pequeño , que incluyen longitudes de ruta promedio cortas y agrupación alta . 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 (Watts) después de que Watts solía formularlo en su libro de divulgación científica Six Degrees .${\ Displaystyle \ beta}$

El estudio formal de gráficos aleatorios se remonta al trabajo de Paul Erdős y Alfréd Rényi . ^[2] Las gráficas que consideraron, ahora conocidas como gráficas clásicas o de Erdős – Rényi (ER) , ofrecen un modelo simple y poderoso con muchas aplicaciones.

El modelo de Watts y Strogatz fue diseñado como el modelo más simple posible que aborda la primera de las dos limitaciones. Tiene en cuenta la agrupación en clústeres al tiempo que conserva las longitudes de ruta medias cortas del modelo ER. Lo hace interpolando entre una estructura aleatoria cercana a los gráficos ER y una red de anillo regular . En consecuencia, el modelo es capaz de explicar al menos parcialmente los fenómenos del "mundo pequeño" en una variedad de redes, como la red eléctrica, la red neuronal de C. elegans , las redes de actores de películas o la comunicación del metabolismo de las grasas en la levadura en ciernes. . ^[4]

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

La estructura de celosía subyacente del modelo produce una red agrupada localmente, mientras que los enlaces recableados aleatoriamente reducen drásticamente las longitudes de ruta promedio . El algoritmo introduce unos de estos bordes sin celosía. La variación permite interpolar entre un retículo regular ( ) y una estructura cercana a un gráfico aleatorio de Erdős-Rényi con at . No se acerca al modelo ER real ya que cada nodo estará conectado al menos a otros nodos.${\ Displaystyle \ beta {\ frac {NK} {2}}}$${\ Displaystyle \ beta}$${\ Displaystyle \ beta = 0}$ ${\ Displaystyle G (N, p)}$${\ Displaystyle p = {\ frac {K} {N-1}}}$${\displaystyle \beta =1}$${\displaystyle K/2}$

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

Modelo de mundo pequeño Watts – Strogatz generado por igraph y visualizado por Cytoscape 2.5. 100 nodos.

Gráfico de Watts-Strogatz