Modelos de redes en evolución del mundo local

Una red evolutiva es una red que cambia con el tiempo. En este tipo de red, los componentes (llamados nodos ) y las conexiones entre ellos (llamadas aristas ) pueden agregarse o eliminarse. Este comportamiento dinámico es una característica clave de muchos sistemas del mundo real. Por ejemplo:

Una red social evoluciona a medida que las personas hacen nuevos amigos, se unen a nuevas comunidades o pierden el contacto con viejos conocidos.

Internet evoluciona a medida que se crean nuevos sitios web y se enlazan entre ellos, mientras que los antiguos se eliminan.
Las redes de transporte evolucionan a medida que se añaden nuevas carreteras o rutas aéreas.

Estudiar cómo evolucionan las redes ayuda a los investigadores a comprender el crecimiento y la estructura de los sistemas complejos. Se han desarrollado diferentes modelos matemáticos para describir estos cambios, cada uno de los cuales refleja reglas distintas sobre cómo se añaden o eliminan nodos y aristas.

Modelos de evolución comunes

La estructura de una red está determinada por el proceso de su evolución. Los principales modelos que describen estos procesos difieren en cómo los nuevos nodos eligen con qué nodos existentes conectarse. Todos los modelos siguientes asumen que los puntos recién agregados tienen información global sobre toda la red, excepto el modelo de mundo local.

Las redes aleatorias siguen el modelo de Erdős-Rényi , donde se añaden nuevos nodos y aristas a la red de forma completamente aleatoria. Este fue uno de los primeros modelos para la evolución de redes. ^{[ 1 ]}
Las redes libres de escala evolucionan mediante un proceso denominado conexión preferencial . En este modelo, los nodos nuevos tienen mayor probabilidad de conectarse a nodos existentes que ya poseen numerosas conexiones, un efecto de " los ricos se hacen más ricos ". Esto crea "centros" altamente conectados y se describe mediante el modelo de Barabási-Albert . ^{[ 2 ]}
Las redes de mundo pequeño se caracterizan por nodos que se agrupan en gran medida en grupos locales, pero que están conectados por caminos cortos a cualquier otro nodo de la red. El modelo de Watts-Strogatz describe redes que no son ni completamente regulares ni completamente aleatorias, pero que poseen esta propiedad de "mundo pequeño".^{[ 3 ]}
Las redes de mundo local explican que, en muchos sistemas grandes, un nuevo nodo solo tiene conocimiento de una pequeña porción local de toda la red. Por lo tanto, establece conexiones basándose en esta información local limitada en lugar de en el conocimiento global. Este concepto fue descrito por primera vez por Li y Chen (2003). El modelo de mundo local fue extendido, entre otros, por Gardeñes y Moreno (2004), Qin y Dai, ^{[ 4 ]} Wen et al. ^{[ 5 ]} o Xuan et al. ^{[ 6 ].}

Modelo de red mundial en evolución de Li y Chen (2003)

El modelo comienza con un conjunto de un número pequeño de nodos. $m_{0}$ y el pequeño número de bordes $e_{0}$ Hay M nodos que fueron seleccionados aleatoriamente de toda la red global, de modo que constituyen un llamado “mundo local” para los nuevos nodos que llegan. Así, cada nuevo nodo con m aristas se conecta solo con m nodos existentes de su mundo local y no se enlaza con nodos que están en el sistema global (la principal diferencia con el modelo BA). En tal caso, la probabilidad de conexión se puede definir como:

P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}

Dónde $P'(i\in Mundo Local)={\frac {M}{m_{0}+t^{}}}$ y el término "Mundo Local" se refiere a todos los nodos que son de interés para el nodo recién agregado en el tiempo t. Por lo tanto, se puede reescribir:

P_{local}'(k_{i})={\frac {M_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}

mientras que la dinámica es:

{\frac {\partial k_{i}}{\partial t}}={\frac {mM_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}

En cada instante t , es cierto que $m\leqslant M\leqslant m_{0}+t$ , de modo que son posibles dos soluciones de esquina: $M=m$ y $M=m_{0}+t$ .

Fig. 1. Comparación de la distribución de grados en escala logarítmica doble del caso límite inferior con M = m = 3, y una red de evolución local-mundial con M = 4 y m = 3. Las redes tienen N = 10 000. El recuadro está en la escala logarítmica lineal de las mismas curvas ^{[ 7 ].}

Caso A. Límite inferior $M=m$

Un nuevo nodo se conecta únicamente a nodos del mundo local M elegido inicialmente. Esto indica que, en el proceso de crecimiento de la red, la selección de conexión preferencial (PA) no es eficiente. El caso es idéntico al del modelo libre de escala BA, en el que la red crece sin PA. La tasa de cambio del grado del i-ésimo nodo se puede expresar de la siguiente manera:

{\frac {\partial k_{i}}{\partial t}}={\frac {m_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}

Por lo tanto, lo anterior demuestra que en la solución de límite inferior, la red tiene una distribución de grados que decae exponencialmente : $P(k)\sim e^{-k/m}$ (Fig. 1)

Caso B Límite inferior $M=m_{0}+t$

En este caso, el mundo local se comporta de la misma manera que la red global. Evoluciona en el tiempo. Por lo tanto, el modelo LW puede compararse con el modelo libre de escala de Barabási-Albert, y la tasa de cambio del grado del nodo 'i' puede expresarse como:

{\frac {\partial k_{i}}{\partial t}}={\frac {k_{i}}{2t}}

Esta igualdad indica que, en la solución del límite superior, el modelo LW sigue la distribución de grados de la ley de potencias: $P(k)\sim 2m^{2}/k^{3}$ (Fig. 2) Por lo tanto, a partir de A y B, se puede encontrar que entre las soluciones de esquina, el modelo de Li y Chen representa una transición para la distribución de grados entre la exponencial y la ley de potencias (Fig. 3).

Nuevo modelo de red evolutiva del mundo local de Qin y Dai (2009)

El modelo es una extensión del modelo LM en el sentido de que divide los nodos en aquellos que tienen información sobre la red global y aquellos que no. Para controlar esta diversificación, el parámetro $\delta$ se introduce. Deje $\delta$ sea la relación entre el número de nodos que obtienen información sobre la red global y el número total de nodos. Porque $\delta$ es una proporción, debe ser que $\delta \in \left[0,1\right]$ . Cuando $\delta =0$ No hay nodos que posean la información global y el modelo NLW se reduce al modelo de red del mundo local. A su vez, $\delta =1$ Esto significa que cada nodo posee la información global sobre la red, lo que hace que el modelo NLW sea idéntico al modelo BA. El modelo NWL comienza de la misma manera que LW: hay un conjunto de un pequeño número de nodos m_0 y un pequeño número de aristas. $e_{0}$ Hay M nodos que fueron seleccionados aleatoriamente de toda la red global y establecieron un “mundo local” para los nuevos nodos entrantes. Sin embargo, en el modelo NLW, cada nuevo nodo con m aristas puede conectarse al sistema global o local. La decisión depende de la información recibida. Si un nuevo nodo obtiene información sobre toda la red, la probabilidad de que se conecte con el nodo i depende del grado ki de ese nodo, de tal manera que:

P_{global}(k_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}

A su vez, si el nodo no fue proporcionado en la información global y solo conoce su mundo local, se conectará solo con nodos de este sistema con la siguiente probabilidad:

P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{j}}{\sum _{j\in Local}k_{j}^{}}}

Por lo tanto, la probabilidad general en el nuevo modelo de mundo local se puede escribir como:

P_{all}'(k_{i})==\delta {\frac {k_{i}}{\sum _{j}k_{j}}}+(1-\delta )P'(i\in Local-World){\frac {k_{i}}{\sum _{j}k_{j}}}

dónde $\delta$ es la probabilidad de que un nuevo nodo posea conocimiento sobre la red global. De manera similar al modelo LW, el modelo NLW distingue tres casos de selección del mundo local:

m=M

;

m\ll M\ll m_{0}+t

y

M=m_{0}+t

El caso límite superior (Caso C) es el mismo que en el modelo del mundo local.

Caso A Límite inferior $M=m$

En el límite inferior, solo unos pocos nodos cumplen con el requisito de conexión preferencial holística, mientras que la mayoría se conectan mediante una nueva arista de forma aleatoria. Además, el grado acumulativo del mundo local depende de la selección aleatoria. En tal caso, la dinámica del sistema se describe mediante:

{\frac {\partial k_{i}}{\partial t}}={\frac {\delta k_{i}+2(1-\delta )m}{2t}}

partiendo de la base de que: $\sum _{j\in local}k_{j}=M\left\langle k_{i}\right\rangle =m\left\langle k_{i}\right\rangle \approx mk_{i}$ En este caso, la distribución de grados de las redes sigue una distribución de potencia baja, y el exponente de la red libre de escala $(\sigma )$ igual $1+{\frac {\delta }{2}}$ de modo que la suposición inicial sobre los pequeños $\delta$ indica que el exponente de potencia baja de la red alcanza un valor alto.

Caso B. $m\ll M\ll m_{0}+t$

En el tiempo hay $m_{0}+t$ nodos Si el nuevo nodo entrante no tiene información sobre la red global, se conectará al nodo i en el sistema local con la probabilidad $M=m_{0}+t$ Por lo tanto, la dinámica se puede escribir de la siguiente manera:

{\frac {\partial k_{i}}{\partial t}}=\left[{\frac {\delta }{2}}-{\frac {1+\delta }{1-\delta }}\right]{\frac {k_{i}}{t}}

partiendo de la base de que: $\sum _{j\in local}k{j}=\sum _{j\in local}k_{j}=\left[\delta \left\langle k_{i}\right\rangle +(1-\delta )m\right]M$ Como en el caso anterior, la red en evolución tiene una distribución de grados de ley de potencias, sin embargo, con un exponente γ mayor, que es igual a : ${\frac {4+\delta +\delta ^{2}}{2-\delta -\delta ^{2}}}$ Puede observarse que el $\delta$ La relación es el único parámetro del exponente libre de escala del nuevo modelo. Por lo tanto, la mejora significativa del modelo proviene de la introducción de $\delta$ , que al agregar o eliminar nodos que poseen información sobre la red global, permite controlar la estructura topológica de una red.

Referencias

↑ P. Erdős y A. Rényi (1961). Sobre la evolución de los gráficos aleatorios, Publ. Matemáticas. Inst. Colgado. Acad. Ciencia, Vol.5, p.17-61
↑ R. Albert y A.-L. Barabasi (2000). Physical Review Letters, Vol. 85, No. 24, pág. 5234
↑ DJ Watts y SH Strogatz (1998). Dinámica colectiva de redes de "mundo pequeño", Nature, vol. 393, págs. 440-442
↑ S. Qin y G. Dai (2009) Chinese Physics B, Vol. 18, No. 2, pág. 383
↑ G. Wen, Z. Duan, G. Chen y X. Geng (2011). Physica A, Vol. 390, pág. 4012
↑ Q. Xuan, Y. Li y T. Wu (2007). Physica A, Vol. 378, pág. 561
↑ X. Li y G. Chen (2003). Physica A, Vol. 328, pág. 274

Fuentes

Bao, Z. y Y. Cao (2008). Revista de Ciencias de la Universidad de Zhejiang A, Vol. 9, No. 10, pág. 1336
Lu, J., H. Leung y G. Chen (2004). Dinámica de sistemas continuos, discretos e impulsivos Serie B: Aplicaciones y algoritmos, Vol. 11a, pág. 70

[1] P. Erdős y A. Rényi (1961). Sobre la evolución de los gráficos aleatorios, Publ. Matemáticas. Inst. Colgado. Acad. Ciencia, Vol.5, p.17-61

[2] R. Albert y A.-L. Barabasi (2000). Physical Review Letters, Vol. 85, No. 24, pág. 5234

[3] DJ Watts y SH Strogatz (1998). Dinámica colectiva de redes de "mundo pequeño", Nature, vol. 393, págs. 440-442

[4] S. Qin y G. Dai (2009) Chinese Physics B, Vol. 18, No. 2, pág. 383

[5] G. Wen, Z. Duan, G. Chen y X. Geng (2011). Physica A, Vol. 390, pág. 4012

[6] Q. Xuan, Y. Li y T. Wu (2007). Physica A, Vol. 378, pág. 561

[7] X. Li y G. Chen (2003). Physica A, Vol. 328, pág. 274

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ].

[ 7 ].

Modelos de evolución comunes

Modelo de red mundial en evolución de Li y Chen (2003)

Caso A. Límite inferiorMETRO=metro{\displaystyle M=m}

Caso B Límite inferiorMETRO=metro0+t{\displaystyle M=m_{0}+t}