Modelo Watts-Strogatz

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

El modelo de 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 propuesta por Duncan J. Watts y Steven Strogatz en su artículo publicado en 1998 en la revista científica Nature. El modelo también se conoció como el modelo beta (Watts) después de que Watts solía $beta$ formularlo en su popular libro de ciencia Six Degrees.

Justificación del modelo

El estudio formal de grafos aleatorios se remonta al trabajo de Paul Erdős y Alfréd Rényi. Los gráficos que consideraron, ahora conocidos como gráficos clásicos o 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 agrupaciones locales ni cierres triádicos. En cambio, debido a que tienen una probabilidad constante, aleatoria e independiente de que se conecten dos nodos, 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 sin escala del mundo real.

El modelo de Watts y Strogatz fue diseñado como el modelo más simple posible que aborda la primera de las dos limitaciones. Da cuenta de la agrupación mientras conserva las longitudes de ruta promedio cortas del modelo ER. Lo hace mediante la interpolación 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 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 cine o la comunicación del metabolismo de las grasas en la levadura en ciernes..

Algoritmo

Dado el número deseado de nodos $norte$ , el grado medio $k$ (que se supone que es un número entero par) y un parámetro especial $beta$ , que satisface $0leqbetaleq 1$ y ${ estilo de visualización N gg K ln N gg 1}$ , el modelo construye un gráfico no dirigido con $norte$ nodos y ${frac{NK}{2}}$ aristas de la siguiente manera:

Construya una red de anillos regular, un gráfico con $norte$ nodos cada uno conectado a $k$ vecinos, $K/2$ en cada lado. Es decir, si los nodos están etiquetados ${displaystyle 0ldots {N-1}}$ , hay una arista $(yo, j)$ si y solo si ${displaystyle 0<|ij| mathrm {mod} left(N-1-{frac {K}{2}}right)leq {frac {K}{2}}.}$
Para cada nodo ${displaystyle i=0,puntos,{N-1}}$ , tome cada borde que se conecta $i$ a sus $K/2$ vecinos más a la derecha, es decir, cada borde ${ estilo de visualización (i, j mathrm {mod} N)}$ con ${displaystyle i<jleq i+K/2}$ , y reconéctelo con probabilidad $beta$ . El recableado se realiza reemplazando ${ estilo de visualización (i, j mathrm {mod} N)}$ con ${ estilo de visualización (i, k)}$ where $k$ se elige uniformemente al azar de todos los nodos posibles mientras se evitan los bucles automáticos ( $kneq yo$ ) y la duplicación de enlaces (no hay borde ${ estilo de visualización (yo, {k'})}$ con $k'=k$ en este punto del algoritmo).

Propiedades

La estructura reticular 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 alrededor $beta {frac{NK}{2}}$ de tales bordes no reticulares. La variación $beta$ permite interpolar entre una red regular ( $beta = 0$ ) y una estructura cercana a un gráfico aleatorio de Erdős-Rényi ${ estilo de visualización G (N, p)}$ con ${displaystyle p={frac{K}{N-1}}}$ at $beta = 1$ . No se acerca al modelo ER real ya que cada nodo estará conectado al menos a ${ estilo de visualización K/2}$ otros nodos.

Las tres propiedades de interés son la longitud de trayectoria promedio, el coeficiente de agrupamiento y la distribución de grados.

Longitud de ruta promedio

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

Coeficiente de agrupamiento

Para la red de anillos, el coeficiente $C(0)={frac{3(K-2)}{4(K-1)}}$ de agrupamiento tiende a $3/4$ crecer $k$ , independientemente del tamaño del sistema. En el caso límite, $beta flecha derecha 1$ el coeficiente de agrupamiento es del mismo orden que el coeficiente de agrupamiento de los gráficos aleatorios clásicos ${ estilo de visualización C = K/(N-1)}$ 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 valores relativamente altos $beta$ . 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".Si usamos la medida de Barrat y Weigt para el agrupamiento $C'(beta)$ definido 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)equiv {frac {3times {text{número de triángulos}}}{text{número de triples conectados}}}}$ 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 $k$ . La distribución de grados para una gran cantidad de nodos y $0<beta<1$ se puede escribir como, ${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)^{kK/2-n}}{(kK/2-n)!}}e^{-beta K/2}, }$

donde $k_{yo}$ es el número de aristas que $yo^{{text{th}}}$ tiene el nodo o su grado. Aquí $kgeq K/2$ , y $f(k,K)=min(kK/2,K/2)$ . La forma de la distribución de grados es similar a la de un gráfico aleatorio y tiene un pico pronunciado $k = k$ y decae exponencialmente para grandes $|kk|$ . 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 suelen ser redes sin escala y de grado no homogéneo, con centros y una distribución de grado sin escala. Tales redes se describen mejor a ese respecto por la familia de modelos de apego preferencial, como el modelo Barabási-Albert (BA). (Por otro lado, el modelo de Barabási-Albert no logra producir los altos niveles de agrupamiento observados 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 totalmente 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.

Contenido relacionado

Más resultados...