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 usópara formularlo en su libro de divulgación científica Six Degrees .
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] 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.
Sin embargo, los gráficos ER no tienen dos propiedades importantes observadas en muchas redes del mundo real:
- No generan clustering 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 .
- No tienen en cuenta la formación de hubs. 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 en clústeres al tiempo que 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 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]
Algoritmo
Dado el número deseado de nodos , el grado medio (se supone que es un número entero par) y un parámetro especial , satisfactorio y , el modelo construye un gráfico no dirigido con nodos y bordes de la siguiente manera:
- Construya una celosía de anillo regular, un gráfico con nodos cada uno conectado a vecinos, en cada lado. Es decir, si los nodos están etiquetados, hay una ventaja si y solo si
- Para cada nodo toma cada borde conectando a su vecinos de la derecha, eso es cada borde con , y vuelva a cablearlo con probabilidad . El recableado se realiza reemplazando con dónde se elige uniformemente al azar de todos los nodos posibles mientras se evitan los bucles automáticos () y duplicación de enlaces (no hay borde con en este punto del algoritmo).
Propiedades
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 sobrede tales bordes sin celosía. Variar permite interpolar entre una celosía regular () y una estructura cercana a un gráfico aleatorio de Erdős-Rényi con a . No se acerca al modelo ER real ya que cada nodo estará conectado al menos a otros nodos.
Las tres propiedades de interés son la longitud de camino promedio , el coeficiente de agrupamiento y la distribución de grados .
Longitud media del camino
Para una red de anillo, la longitud de camino promedio [1] esy escala linealmente con el tamaño del sistema. En el caso límite de, la gráfica se aproxima a una gráfica aleatoria con , aunque en realidad no converge con él. En la región intermedia, la longitud media de la trayectoria cae muy rápidamente al aumentar , acercándose rápidamente a su valor límite.
Coeficiente de agrupamiento
Para la red de anillo, el coeficiente de agrupamiento [5] , y así tiende a como 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 gráficos aleatorios clásicos, y por 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 celosía regular, y solo cae a niveles relativamente altos.. Esto da como resultado una región donde la longitud promedio de la trayectoria cae rápidamente, pero el coeficiente de agrupamiento no lo hace, lo que explica el fenómeno del "mundo pequeño".
- Si usamos la medida de Barrat y Weigt [6] para agrupar definida como la fracción entre el número medio de aristas entre los vecinos de un nodo y el número medio de aristas posibles entre estos vecinos o, alternativamente,
- entonces tenemos
Distribución de titulaciones
La distribución de grados en el caso de la red de anillo es solo una función delta de Dirac centrada en. La distribución de grados para un gran número de nodos yse puede escribir como, [6]
dónde es el número de aristas que nodo tiene 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 grandes . La topología de la red es relativamente homogénea, lo que significa que todos los nodos tienen un grado similar.
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, no homogéneas en grado, que tienen hubs y una distribución de grados sin escala. En ese sentido, estas redes se describen mejor mediante la familia de modelos de apego preferencial , como el modelo Barabási-Albert (BA) . (Por otro lado, el modelo Barabási-Albert no logra producir los altos niveles de agrupamiento observados en redes reales, una deficiencia que no comparten el modelo Watts y Strogatz. Por lo tanto, ni el modelo Watts y Strogatz ni el modelo 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 lo tanto, no se puede utilizar para modelar el crecimiento de la red.
Ver también
Referencias
- ^ a b Watts, DJ ; Strogatz, SH (1998). "Dinámica colectiva de las redes de 'pequeños mundos'" (PDF) . Naturaleza . 393 (6684): 440–442. Código Bibliográfico : 1998Natur.393..440W . doi : 10.1038 / 30918 . PMID 9623998 .
- ^ Erdos, P. (1960). "Publicaciones Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Matemáticas. Inst. Colgado. Acad. Sci . 5 : 17.
- ^ Ravasz, E. (30 de agosto de 2002). "Organización jerárquica de modularidad en redes metabólicas". Ciencia . 297 (5586): 1551-1555. arXiv : cond-mat / 0209244 . Código Bibliográfico : 2002Sci ... 297.1551R . doi : 10.1126 / science.1073374 . PMID 12202830 .
- ^ 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 Biología Computacional . 11 (5): e1004264. Código bibliográfico : 2015PLSCB..11E4264A . doi : 10.1371 / journal.pcbi.1004264 . PMC 4447291 . PMID 26020510 .
- ^ 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 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b c Barrat, A .; Weigt, M. (2000). "Sobre las propiedades de los modelos de redes de pequeños mundos". Diario Europea de Física B . 13 (3): 547–560. arXiv : cond-mat / 9903411 . doi : 10.1007 / s100510050067 .