Modelo de Watts-Strogatz

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de red
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neurona artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Bucle Vecindario Camino Vértice Lista  / matriz de adyacencia Listado  / matriz de incidencias Tipos Bipartito Completo Dirigido Hyper Labeled Multi Random Weighted
Metrics Algorithms
Centrality Degree Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

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 trayectoria 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 lo formulara en su libro de divulgación científica Six Degrees .${\displaystyle \beta }$

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 grafos clásicos o grafos de Erdős–Rényi (ER) , ofrecen un modelo simple y poderoso con muchas aplicaciones.

Sin embargo, los gráficos ER no tienen dos propiedades importantes observadas 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 gráficos ER tienen un coeficiente de agrupamiento bajo .
2. No tienen en cuenta la formación de ejes. Formalmente, la distribución de grados de los gráficos ER converge a una distribución de Poisson , en lugar de una ley de potencia observada en muchas redes libres de escala del mundo real . ^[3]

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 mientras conserva las longitudes de ruta promedio cortas del modelo ER. Lo hace interpolando entre una estructura aleatoria cercana a los gráficos ER y una red de anillos regular . En consecuencia, el modelo puede explicar al menos parcialmente los fenómenos de "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 (que se supone que es un entero par) y un parámetro , todos satisfactorios 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}}}$

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

La estructura reticular subyacente del modelo produce una red agrupada localmente, mientras que los enlaces reconectados aleatoriamente reducen drásticamente las longitudes de ruta promedio . El algoritmo introduce aproximadamente de estos bordes no reticulares. La variación permite interpolar entre una red regular ( ) y una estructura cercana a un gráfico aleatorio de Erdős–Rényi con en . No se aproxima 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 ruta promedio , el coeficiente de agrupamiento y la distribución de grados .

Para una red en anillo, la longitud de trayectoria promedio ^[1] es y escala linealmente con el tamaño del sistema. En el caso límite de , el gráfico se aproxima a un gráfico aleatorio con , aunque en realidad no converge hacia él. En la región intermedia , la longitud de trayectoria promedio cae muy rápidamente al aumentar , acercándose rápidamente a su valor límite.${\displaystyle \ell (0)\approx N/2K\gg 1}$${\displaystyle \beta \rightarrow 1}$${\displaystyle \ell (1)\approx {\frac {\ln N}{\ln K}}}$${\displaystyle 0<\beta <1}$${\displaystyle \beta }$

Para la red en anillo, el coeficiente de agrupamiento ^[5] , y por lo tanto tiende a a medida que crece, independientemente del tamaño del sistema. ^[6] En el caso límite de , el coeficiente de agrupamiento es del mismo orden que el coeficiente de agrupamiento para grafos aleatorios clásicos y, por lo tanto, es inversamente proporcional al tamaño del sistema. En la región intermedia, el coeficiente de agrupamiento permanece bastante cerca de su valor para la red regular y solo cae a relativamente alto . Esto da como resultado una región donde la longitud de ruta promedio cae rápidamente, pero el coeficiente de agrupamiento no, lo que explica el fenómeno del "mundo pequeño".${\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}$${\displaystyle 3/4}$${\displaystyle K}$${\displaystyle \beta \rightarrow 1}$${\displaystyle C=K/(N-1)}$${\displaystyle \beta }$

Si utilizamos la medida de Barrat y Weigt ^[6] para agrupamiento definida como la fracción entre el número promedio de aristas entre los vecinos de un nodo y el número promedio de aristas posibles entre estos vecinos, o, alternativamente,${\displaystyle C'(\beta )}$

${\displaystyle C'(\beta )\equiv {\frac {3\times {\text{number of triangles}}}{\text{number of connected triples}}}}$

entonces obtenemos${\displaystyle C'(\beta )\sim C(0)(1-\beta )^{3}.}$

La distribución de grados en el caso de la red de anillos es simplemente una función delta de Dirac centrada en . La distribución de grados para una gran cantidad de nodos y se puede escribir como, ^[6]${\displaystyle K}$${\displaystyle 0<\beta <1}$

${\displaystyle P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!}}e^{-\beta K/2},}$

donde es el número de aristas que tiene el nodo o su grado. Aquí , y . La forma de la distribución de grados es similar a la de un gráfico aleatorio y tiene un pico pronunciado en y decae exponencialmente para valores grandes de . La topología de la red es relativamente homogénea, lo que significa que todos los nodos tienen un grado similar.${\displaystyle k_{i}}$${\displaystyle i^{\text{th}}}$${\displaystyle k\geq K/2}$${\displaystyle f(k,K)=\min(k-K/2,K/2)}$${\displaystyle k=K}$${\displaystyle |k-K|}$

La principal limitación del modelo es que produce una distribución de grados poco realista . Por el contrario, las redes reales suelen ser redes sin escala que no son homogéneas en grado, ya que tienen centros y una distribución de grados sin escala. En ese sentido, dichas redes se describen mejor mediante la familia de modelos de unión preferencial , como el modelo Barabási-Albert (BA) . (Por otro lado, el modelo Barabási-Albert no produce los altos niveles de agrupamiento que se observan en las 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 modelo 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 se puede utilizar para modelar el crecimiento de la red.

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