Modelo de Watts-Strogatz

Método para generar gráficos aleatorios de mundo pequeño

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

El modelo de Watts-Strogatz es un modelo de generación de grafos aleatorios 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 }$

Justificación del modelo

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]

Algoritmo

Gráfico de Watts-Strogatz

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}$

Propiedades

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 .

Longitud media del camino

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 }$

Coeficiente de agrupamiento

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}.}$

Distribución de grados

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|}$

Limitaciones

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.

Véase también

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

Referencias

1. Watts, DJ ; Strogatz, SH (1998). «Dinámica colectiva de redes de «mundo pequeño»» (PDF) . Nature . 393 (6684): 440–442. Bibcode :1998Natur.393..440W. doi :10.1038/30918. PMID  9623998. S2CID  4429113. Archivado (PDF) desde el original el 2020-10-26 . Consultado el 2018-05-18 .
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". Science . 297 (5586): 1551–1555. arXiv : cond-mat/0209244 . Bibcode :2002Sci...297.1551R. doi :10.1126/science.1073374. PMID  12202830. S2CID  14452443.
4. Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). "Análisis experimental y computacional de una gran red de proteínas que controla el almacenamiento de grasa revela los principios de diseño de una red de señalización". PLOS Computational Biology . 11 (5): e1004264. Bibcode :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 Bibliográfico :2002RvMP...74...47A. doi :10.1103/RevModPhys.74.47. S2CID  60545.{{cite journal}}: CS1 maint: multiple names: authors list (link)
6. Barrat, A.; Weigt, M. (2000). "Sobre las propiedades de los modelos de redes de mundo pequeño". European Physical Journal B . 13 (3): 547–560. arXiv : cond-mat/9903411 . doi :10.1007/s100510050067. S2CID  13483229.