Modelo Watts y Strogatz
El modelo Watts y Strogatz, en teoría de redes, se emplea para la construcción de algunas redes de mundo pequeño. Genéricamente se trata de un modelo de generación de grafos aleatorios con distancias medias pequeñas y valores altos del coeficiente de agrupamiento (clustering coefficient).[1] El modelo matemático toma el nombre de la investigación realizada por los matemáticos Duncan Watts y Steven Strogatz en el año 1998 en la revista Nature. El estudio formal de los grafos aleatorios se remonta a los estudios de Paul Erdős y Alfréd Rényi.[2] en lo que se denomina Modelo Erdős–Rényi.
Fundamento
El algoritmo de construcción propuesto por watts y strogatz para las redes de mundo pequeño es el siguiente: se establece una red inicial unidimensional con N nodos, estos nodos se pueden disponer en forma de anillo de tal forma que cada uno de los vértices (o nodos) se una con 2k vecinos. La probabilidad de conectar un nodo con otro cualquiera es de p. Para un grafo con p=0 se puede ver que la conectividad es la misma y de valor 2k. por otro lado un valor no nulo de p introduce desorden en la red de tal forma que la conectividad no es uniforme, manteniendo todavía de media un valor de 2k.
Propiedades del modelo
- La distribución de grado de los grafos generados mediante este algoritmo depende del valor de p. En el caso de p=0, en el que la red generada es una red regular, la distribución de grado es una Delta de Dirac centrada en 2k. En el caso de p=1, en el que la red generada es una red aleatoria, la distribución de grado es una distribución de Poisson.
Referencias
- Watts, D.J.; Strogatz, S.H. (1998). «Collective dynamics of 'small-world' networks.». Nature 393 (6684): 440-2. doi:10.1038/30918. Consultado el 25 de febrero de 2008.
- Erdos, P. (1960). «Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi». Publ. Math. Inst. Hung. Acad. Sci 5: 17.