Modelo de Watts-Strogatz

Método de generación de gráficos aleatorios de mundos pequeños.

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

El modelo Watts-Strogatz es un modelo de generación de gráficos aleatorios que produce gráficos con propiedades de mundo pequeño , incluidas longitudes de ruta 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 (Watts) después de que Watts lo formulara en su libro de divulgación científica Six Degrees . ${\displaystyle \beta }$

Justificación del modelo

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

Sin embargo, los gráficos ER no tienen dos propiedades importantes que se observan en muchas redes del mundo real:

1. No generan agrupaciones locales 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 agrupación bajo .
2. No tienen en cuenta la formación de centros. 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 sin 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 y al mismo tiempo conserva las cortas longitudes de ruta promedio 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 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 levaduras en ciernes. . ^[4]

Algoritmo

Gráfico de Watts-Strogatz

Dado el número deseado de nodos , el grado medio (se supone que es un número 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 gráfico con nodos, cada uno de ellos conectado a vecinos, en cada lado. Es decir, si los nodos están etiquetados , hay una arista si y sólo 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 conecte con sus vecinos más a la derecha, es decir, cada borde tal que , y vuelva a cablearlo con probabilidad . El recableado se realiza reemplazando con donde se elige uniformemente al azar de todos los nodos posibles, evitando al mismo tiempo los bucles automáticos ( ) y la duplicación de enlaces (no hay ninguna ventaja 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}$

Propiedades

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

Longitud media del camino

Para una red de anillos, la longitud promedio del camino ^[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 a él. En la región intermedia , la longitud media del camino 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 }$

Coeficiente de agrupamiento

Para la red de anillos, el coeficiente de agrupamiento ^[5] tiende a crecer , independientemente del tamaño del sistema. ^[6] En el caso límite, el coeficiente de agrupamiento es del mismo orden que el coeficiente de agrupamiento para gráficos 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 cercano a su valor para la red regular y solo cae a niveles relativamente altos . Esto da como resultado una región donde la longitud promedio del camino 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 usamos 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}.}$

Distribución de grados

La distribución de grados en el caso de la red anular es simplemente una función delta de Dirac centrada en . La distribución de grados para una gran cantidad de nodos 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 y decae exponencialmente para grandes . 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|}$

Limitaciones

La principal limitación del modelo es que produce una distribución de grados poco realista . Por el contrario, las redes reales son a menudo redes sin escala y de grado no homogéneo, que tienen centros y una distribución de grados sin escala. Estas redes se describen mejor a ese respecto mediante la familia de modelos de apego preferencial , como el modelo de Barabási-Albert (BA) . (Por otro lado, el modelo de Barabási-Albert no logra producir 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 de Barabási-Albert deberían ser visto como completamente realista.)

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

Ver también

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

Referencias

1. Watts, DJ ; Strogatz, SH (1998). "Dinámica colectiva de redes de 'mundos pequeños'" (PDF) . Naturaleza . 393 (6684): 440–442. Código Bib :1998Natur.393..440W. doi :10.1038/30918. PMID  9623998. S2CID  4429113. Archivado (PDF) desde el original el 26 de octubre de 2020 . Consultado el 18 de mayo de 2018 .
2. Erdos, P. (1960). "Publicaciones Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Matemáticas. Inst. Colgado. Acad. Ciencia . 5 : 17.
3. Ravasz, E. (30 de agosto de 2002). "Organización Jerárquica de la Modularidad en Redes Metabólicas". Ciencia . 297 (5586): 1551-1555. arXiv : cond-mat/0209244 . Código bibliográfico : 2002 Ciencia... 297.1551R. doi : 10.1126/ciencia.1073374. PMID  12202830. S2CID  14452443.
4. Al-Anzi, Bader; Arpp, Patricio; Gerges, Sherif; Ormerod, Cristóbal; Olsman, Noé; Zinn, Kai (2015). "El análisis experimental y computacional de una gran red de proteínas que controla el almacenamiento de grasas revela los principios de diseño de una red de señalización". PLOS Biología Computacional . 11 (5): e1004264. Código Bib : 2015PLSCB..11E4264A. doi : 10.1371/journal.pcbi.1004264 . PMC 4447291 . PMID  26020510. 
5. Albert, R., Barabási, A.-L. (2002). "Mecánica estadística de redes complejas". Reseñas de Física Moderna . 74 (1): 47–97. arXiv : cond-mat/0106096 . Código Bib : 2002RvMP...74...47A. doi :10.1103/RevModPhys.74.47. S2CID  60545.{{cite journal}}: CS1 maint: multiple names: authors list (link)
6. Barrat, A.; Peso, M. (2000). "Sobre las propiedades de los modelos de redes de mundos pequeños". Revista física europea B. 13 (3): 547–560. arXiv : cond-mat/9903411 . doi :10.1007/s100510050067. S2CID  13483229.