Hispanopedia Wiki
Articulo de referencia

Robustez de las redes complejas

La robustez , la capacidad de resistir fallos y perturbaciones , es un atributo fundamental de muchos sistemas complejos , incluidas las redes complejas . El estudio de la robus...

Hispanopedia WikiContenido en espanolLectura gratuita

La robustez , la capacidad de resistir fallos y perturbaciones , es un atributo fundamental de muchos sistemas complejos , incluidas las redes complejas .

El estudio de la robustez en redes complejas es importante para muchos campos. En ecología , la robustez es un atributo importante de los ecosistemas y puede brindar información sobre la reacción a perturbaciones como la extinción de especies. [ 1 ] Para los biólogos , la robustez de la red puede ayudar al estudio de enfermedades y mutaciones , y cómo recuperarse de algunas mutaciones. [ 2 ] En economía , los principios de robustez de la red pueden ayudar a comprender la estabilidad y los riesgos de los sistemas bancarios. [ 3 ] Y en ingeniería , la robustez de la red puede ayudar a evaluar la resiliencia de redes de infraestructura como Internet o las redes eléctricas . [ 4 ]

teoría de la percolación

El foco de la robustez en redes complejas es la respuesta de la red a la eliminación de nodos o enlaces. El modelo matemático de dicho proceso puede considerarse como un proceso de percolación inversa. La teoría de la percolación modela el proceso de colocar aleatoriamente guijarros en una red n-dimensional con probabilidad p, y predice la formación repentina de un único gran cúmulo en una probabilidad crítica.pagdo{\displaystyle p_{c}}. [ 5 ] En la teoría de la percolación, este grupo se denomina grupo percolante. Este fenómeno se cuantifica en la teoría de la percolación mediante una serie de cantidades, por ejemplo, el tamaño promedio del grupo.⟨s⟩{\displaystyle \langle s\rangle }. Esta cantidad representa el tamaño promedio de todos los cúmulos finitos y viene dada por la siguiente ecuación.

⟨s⟩∼|pag−pagdo|γpag{\displaystyle {\begin{aligned}\langle s\rangle \sim \left|p-p_{c}\right|^{\gamma _{p}}\end{aligned}}}

Podemos observar que el tamaño promedio del clúster diverge repentinamente alrededor de la probabilidad crítica, lo que indica la formación de un único clúster grande. También es importante tener en cuenta que el exponenteγpag{\displaystyle \gamma _{p}}es universal para todas las redes, mientras quepagdo{\displaystyle p_{c}}No lo es. Esto es importante, ya que indica un comportamiento de transición de fase universal , en un punto que depende de la topología. El problema de la robustez en redes complejas puede considerarse como el inicio del clúster percolante, al que se le quita una fracción crítica de nodos para que se desintegre. De forma análoga a la formación del clúster de percolación en la teoría de la percolación, la desintegración de una red compleja ocurre abruptamente durante una transición de fase al eliminarse una fracción crítica de nodos.

Umbral crítico para fallos aleatorios

La derivación matemática del umbral en el que una red compleja perderá su componente gigante se basa en el criterio de Molloy-Reed . [ 6 ]

κ≡⟨k2⟩⟨k⟩>2{\displaystyle {\begin{aligned}\kappa \equiv {\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2\end{aligned}}}

El criterio de Molloy-Reed se deriva del principio básico de que, para que exista un componente gigante, en promedio cada nodo de la red debe tener al menos dos enlaces. Esto es análogo a que cada persona tome de la mano a otras dos para formar una cadena. Utilizando este criterio y una demostración matemática compleja , se puede derivar un umbral crítico para la fracción de nodos que deben eliminarse para que se produzca la ruptura del componente gigante de una red compleja. [ 7 ]

Fdo=1−1⟨k2⟩⟨k⟩−1{\displaystyle {\begin{aligned}f_{c}=1-{\frac {1}{{\frac {\langle k^{2}\rangle }{\langle k\rangle }}-1}}\end{aligned}}}

Una propiedad importante de este hallazgo es que el umbral crítico solo depende del primer y segundo momento de la distribución de grados y es válido para una distribución de grados arbitraria.

Red aleatoria

Usando⟨k2⟩=⟨k⟩(⟨k⟩+1){\displaystyle \langle k^{2}\rangle =\langle k\rangle (\langle k\rangle +1)}Para un grafo aleatorio de Erdős-Rényi (ER) , se puede reexpresar el punto crítico para una red aleatoria . [ 8 ]

FdomiR=1−1⟨k⟩{\displaystyle {\begin{aligned}f_{c}^{ER}=1-{\frac {1}{\langle k\rangle }}\end{aligned}}}

A medida que una red aleatoria se vuelve más densa, el umbral crítico aumenta, lo que significa que se debe eliminar una mayor fracción de nodos para desconectar el componente gigante.

Red libre de escala

Al reexpresar el umbral crítico como una función del exponente gamma para una red libre de escala , podemos extraer un par de conclusiones importantes con respecto a la robustez de las redes libres de escala. [ 8 ]

Fdo=1−1κ−1κ=⟨k2⟩⟨k⟩=|2−γ3−γ|AA=Kmetroinorte, γ>3A=Kmetroaincógnita3−γKmetroinorteγ−2, 3>γ>2A=Kmetroaincógnita, 2>γ>1whmirmi Kmetroaincógnita=Kmetroinortenorte1γ−1{\displaystyle {\begin{aligned}f_{c}&=1-{\frac {1}{\kappa -1}}\\\kappa &={\frac {\langle k^{2}\rangle }{\langle k\rangle }}=\left|{\frac {2-\gamma }{3-\gamma }}\right|A\\A&=K_{min},~\gamma >3\\A&=K_{max}^{3-\gamma }K_{min}^{\gamma -2},~3>\gamma >2\\A&=K_{max},~2>\gamma >1\\&where~K_{max}=K_{min}N^{\frac {1}{\gamma -1}}\end{aligned}}}

Paraγ>3{\displaystyle \gamma >3}, el umbral crítico solo depende de gamma y del grado mínimo, y en este régimen la red actúa como una red aleatoria que se rompe cuando se elimina una fracción finita de sus nodos. Paraγ<3{\displaystyle \gamma <3},κ{\displaystyle \kappa }diverge en el límite cuando N tiende a infinito. En este caso, para grandes redes libres de escala, el umbral crítico se aproxima a 1. Esto significa esencialmente que casi todos los nodos deben eliminarse para destruir el componente gigante, y las grandes redes libres de escala son muy robustas con respecto a fallas aleatorias. Se puede comprender intuitivamente esta conclusión al pensar en la heterogeneidad de las redes libres de escala y de los nodos centrales en particular. Debido a que hay relativamente pocos nodos centrales, es menos probable que se eliminen por fallas aleatorias, mientras que los nodos pequeños de bajo grado tienen más probabilidades de ser eliminados. Dado que los nodos de bajo grado son de poca importancia para conectar el componente gigante, su eliminación tiene poco impacto.

Ataques dirigidos a redes libres de escala

Aunque las redes libres de escala son resistentes a fallos aleatorios, podríamos imaginar que son bastante vulnerables a la eliminación dirigida de nodos centrales. En este caso, consideramos la robustez de las redes libres de escala frente a ataques dirigidos, realizados con un conocimiento previo exhaustivo de la topología de la red . Al considerar los cambios inducidos por la eliminación de un nodo central, específicamente el cambio en el grado máximo y los grados de los nodos conectados, podemos derivar otra fórmula para el umbral crítico considerando ataques dirigidos en una red libre de escala. [ 9 ]

Fdo2−γ1−γ=2+2−γ3−γKmetroinorte(Fdo3−γ1−γ−1){\displaystyle {\begin{aligned}f_{c}^{\frac {2-\gamma }{1-\gamma }}=2+{\frac {2-\gamma }{3-\gamma }}K_{min}(f_{c}^{\frac {3-\gamma }{1-\gamma }}-1)\end{aligned}}}

Esta ecuación no se puede resolver analíticamente, pero sí se puede graficar numéricamente. En resumen, cuando gamma es grande, la red se comporta como una red aleatoria y su robustez ante ataques se asemeja a la de una red aleatoria con fallos aleatorios. Sin embargo, cuando gamma es menor, el umbral crítico para ataques en redes libres de escala se reduce considerablemente, lo que indica una vulnerabilidad ante ataques dirigidos.

Para obtener información más detallada sobre la tolerancia a los ataques de las redes complejas, consulte la página de tolerancia a los ataques .

Fallos en cascada

Un aspecto importante de las fallas en muchas redes es que una sola falla en un nodo puede inducir fallas en nodos vecinos. Cuando un pequeño número de fallas induce más fallas, resultando en un gran número de fallas en relación con el tamaño de la red, se ha producido una falla en cascada . Hay muchos modelos para fallas en cascada. [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] Estos modelos difieren en muchos detalles y modelan diferentes fenómenos de propagación física, desde fallas de energía hasta el flujo de información en Twitter , pero tienen algunos principios compartidos. Cada modelo se centra en algún tipo de propagación o cascada, hay algún umbral que determina cuándo un nodo fallará o se activará y contribuirá a la propagación, y hay algún mecanismo definido por el cual se dirigirá la propagación cuando los nodos fallen o se activen. Todos estos modelos predicen un estado crítico en el que la distribución del tamaño de las cascadas potenciales se ajusta a una ley de potencias , y el exponente está determinado de forma unívoca por el exponente de grado de la red subyacente. Debido a las diferencias entre los modelos y al consenso sobre este resultado, se nos lleva a creer que el fenómeno subyacente es universal e independiente del modelo. [ 8 ]

Para obtener información más detallada sobre la modelización de fallos en cascada, consulte la página del modelo global de cascadas .

Referencias

  1. ↑ VR Sole; MM Jose (2001). "Complejidad y fragilidad en redes ecológicas" . Proc. R. Soc. Lond. B. 268 ( 1480): 2039–45 . arXiv : cond-mat/0011196 . doi : 10.1098 /rspb.2001.1767 . PMC 1088846. PMID 11571051 .  
  2. ↑ A. Motter; N. Gulbahce; E. Almaas y A.-L. Barabási (2008). "Predicción de rescates sintéticos en redes metabólicas" . Biología de Sistemas Moleculares . 4 : 1–10 . arXiv : 0803.0962 . doi : 10.1038/msb.2008.1 . PMC 2267730. PMID 18277384 .  
  3. ↑ Haldane, AG; May, RM (2011). "Riesgo sistémico en los ecosistemas bancarios". Nature . 469 ( 7330): 351– 355. Bibcode : 2011Natur.469..351H . CiteSeerX 10.1.1.418.6489 . doi : 10.1038/nature09659 . PMID 21248842. S2CID 8264608 .   
  4. ↑ Albert, R.; Albert, I.; Nakarado, GL (2004). "Vulnerabilidad estructural de la red eléctrica norteamericana". Phys. Rev. E . 69 (2) 025103. arXiv : cond-mat/0401084 . Bibcode : 2004PhRvE..69b5103A . doi : 10.1103/physreve.69.025103 . PMID 14995510 . S2CID 18811015 .  
  5. ↑ D. Stauffer y A. Aharony. Introducción a la teoría de la percolación. Taylor and Francis. Londres, 1994.
  6. ↑ Molloy, M. y Reed, B. (1995) Estructuras aleatorias y algoritmos 6 , 161–180.
  7. ↑ Cohen, R.; Erez, K.; Havlin, S. (2000). "Resiliencia de Internet ante fallos aleatorios". Phys. Rev. Lett . 85 (21): 4626– 4628. arXiv : cond-mat/0007048 . Bibcode : 2000PhRvL..85.4626C . doi : 10.1103 /physrevlett.85.4626 . PMID 11082612. S2CID 15372152 .  
  8. 1 2 3 ALBERT-LÁSZLÓ BARABÁSI. Ciencia de redes (2014).
  9. ↑ Cohen, R.; Erez, K.; ben-Avraham, D.; Havlin, S. (2001). "Colapso de Internet bajo ataque intencional". Phys. Rev. Lett . 86 (16): 3682– 3685. arXiv : cond-mat/0010251 . Bibcode : 2001PhRvL..86.3682C . doi : 10.1103 /physrevlett.86.3682 . PMID 11328053. S2CID 3852896 .  
  10. ↑ Dobson, I.; Carreras, BA; Lynch, VE; Newman, DE (2007). "Análisis de sistemas complejos de series de apagones: fallas en cascada, puntos críticos y autoorganización" . Chaos . 17 (2): 026103. Bibcode : 2007Chaos..17b6103D . doi : 10.1063/1.2737822 . PMID 17614690 . 
  11. ↑ Dobson, I.; Carreras, A.; Newman, DE "Un modelo dependiente de la carga de fallas en cascada probabilísticas. Probabilidad en la". Ingeniería y Ciencias de la Información . 19 (15): 2005.
  12. ↑ Watts, DJ (2002). " Un modelo simple de cascadas globales en redes aleatorias" . PNAS . 99 (9): 5766– 5771. Bibcode : 2002PNAS...99.5766W . doi : 10.1073/pnas.082090499 . PMC 122850. PMID 16578874 .  
  13. ↑ Goh, K.-I.; Lee, D.-S.; Kahng, B.; Kim, D. (2003). "Sandpile on scale-free net-works". Phys. Rev. Lett . 91 (14) 148701. arXiv : cond-mat/0305425 . Bibcode : 2003PhRvL..91n8701G . doi : 10.1103/physrevlett.91.148701 . PMID 14611564 . S2CID 6042619 .  
  14. ↑ Lee, D.-S.; Goh, K.-I.; Kahng, B.; Kim, D. (2004). "Dinámica de avalanchas de pilas de arena en redes libres de escala". Physica A . 338 ( 1– 2): 84. arXiv : cond-mat/0401531 . Bibcode : 2004PhyA..338...84L . doi : 10.1016/j.physa.2004.02.028 . S2CID 14550686 . 
  15. ↑ Ding, M.; Yang, W. (1995). "Distribución del primer tiempo de retorno en el movimiento browniano fraccional y su aplicación al estudio de la intermitencia onoff". Phys. Rev. E . 52 (1): 207– 213. Bibcode : 1995PhRvE..52..207D . doi : 10.1103/physreve.52.207 . PMID 9963421 . 
  16. ↑ Motter, Adilson E.; Lai, Ying-Cheng (20 de diciembre de 2002). "Ataques basados ​​en cascadas en redes complejas". Physical Review E . 66 (6) 065102. arXiv : cond-mat/0301086 . Bibcode : 2002PhRvE..66f5102M . doi : 10.1103/PhysRevE.66.065102 . PMID 12513335 . S2CID 17189308 .  
  17. ↑ Kong, Z.; Yeh, EM (2010). "Resiliencia a fallas de nodos dependientes del grado y en cascada en redes geométricas aleatorias". IEEE Transactions on Information Theory . 56 (11): 5533. doi : 10.1109/tit.2010.2068910 . S2CID 27573946 .