Propiedades estructurales de la solidez de una red a ataques

Tolerancia de errores y ataques de redes complejas

Nature 406, 378-382 (27 July 2000) |
doi:10.1038/35019019;
Received 14 February 2000; Accepted 7 June 2000

Réka Albert, Hawoong Jeong & Albert-László Barabási

Department of Physics, 225 Nieuwland Science Hall, University of Notre Dame, Notre Dame, Indiana 46556, USA
Correspondence to: Albert-László Barabási Correspondence and requests for materials should be addressed to A.-L.B. (e-mail: Email: alb@nd.edu).

Muchos sistemas complejos muestran un sorprendente grado de tolerancia frente a errores. Por ejemplo, los organismos relativamente simples crecen, persisten y se reproducen a pesar de las drásticas intervenciones farmacéuticas o ambientales, una tolerancia de error atribuida a la robustez de la red metabólica subyacente1. Las complejas redes de comunicación2 muestran un sorprendente grado de robustez: aunque los componentes clave regularmente fallan, los fallos locales raramente llevan a la pérdida de la capacidad global de transmisión de información de la red. La estabilidad de estos y otros sistemas complejos se atribuye a menudo al cableado redundante de la red funcional definida por los componentes de los sistemas. Aquí se demuestra que la tolerancia de error no es compartida por todos los sistemas redundantes: sólo se muestra por una clase de redes no homogéneas, denominadas redes sin escala, que incluyen las redes World Wide Web3, 4, 5, Internet6, redes sociales7 y células8. Encontramos que tales redes muestran un grado inesperado de robustez, la capacidad de sus nodos para comunicarse no siendo afectada incluso por tasas de fracaso realistas. Sin embargo, la tolerancia de errores tiene un alto precio ya que estas redes son extremadamente vulnerables a ataques (es decir, a la selección y remoción de algunos nodos que juegan un papel vital en el mantenimiento de la conectividad de la red). Tal tolerancia de error y vulnerabilidad de ataque son propiedades genéricas de las redes de comunicación.

La creciente disponibilidad de datos topológicos sobre las grandes redes, ayudada por la informatización de la adquisición de datos, ha llevado a grandes avances en nuestra comprensión de los aspectos genéricos de la estructura y el desarrollo de la red9,10,11,12,13,14,15,16. Los resultados empíricos y teóricos existentes indican que las redes complejas pueden dividirse en dos clases principales basadas en su distribución de conectividad P (k), dando la probabilidad de que un nodo en la red esté conectado a k otros nodos. La primera clase de redes se caracteriza por un P (k) que alcanza un pico en una valla de cerca de valla media derecha y disminuye exponencialmente para k grande. Los ejemplos más investigados de tales redes exponenciales son el modelo de gráfico aleatorio de Erdös y Rényi9, y el modelo de Watts y Strogatz11 de pequeño mundo, que conduce a una red bastante homogénea, en la que cada nodo tiene aproximadamente el mismo número de enlaces, K sime fencekright cerca de la izquierda. Por el contrario, los resultados obtenidos en la World Wide Web (WWW) 3, 4, 5, Internet6 y otras grandes redes17,18,19 indican que muchos sistemas pertenecen a una clase de redes no homogéneas, denominadas redes libres de escala, para las cuales P (K) decae como una ley de potencia, que es P (k) aproximadamente k-gamma,  P( k)  k libre de una escala característica. Mientras que la probabilidad de que un nodo tenga un número muy grande de conexiones (k doble mayor que la cerca de valla de cerca izquierda) está prácticamente prohibida en redes exponenciales, los nodos altamente conectados son estadísticamente significativos en redes libres de escala.^-




A, La red exponencial es homogénea: la mayoría de los nodos tienen aproximadamente el mismo número de enlaces. B, La red libre de escala es no homogénea: la mayoría de los nodos tienen uno o dos enlaces, pero unos pocos nodos tienen un gran número de enlaces, lo que garantiza que el sistema está totalmente conectado. Rojo, los cinco nodos con el mayor número de enlaces; Verdes, sus primeros vecinos. Aunque en la red exponencial sólo el 27% de los nodos son alcanzados por los cinco nodos más conectados, en la red libre de escala se alcanzan más del 60%, lo que demuestra la importancia de los nodos conectados en la red libre de escala. Nodos y 215 enlaces ((k  = 3.3). La visualización de la red se realizó utilizando el programa Pajek para el análisis de redes de gran tamaño: valla izquierda http://vlado.fmf.uni-lj.si/pub/networks/pajek/pajekman.htmright fence.

Comenzamos por investigar la robustez de los dos modelos básicos de distribución de conectividad, el modelo Erdös-Rényi (ER) 9, 10 que produce una red con cola exponencial y el modelo libre de escala17 con una cola de poder-ley. En el modelo ER primero definimos los N nodos, y luego conectamos cada par de nodos con la probabilidad p. Este algoritmo genera una red homogénea (Fig. 1), cuya conectividad sigue una distribución de Poisson que alcanzó un pico en la valla de cerca de valla izquierda y que se desintegra exponencialmente para k doble mayor que k  k .

La distribución de conectividad no homogénea de muchas redes reales es reproducida por el modelo libre de escala17, 18 que incorpora dos ingredientes comunes a las redes reales: el crecimiento y el apego preferencial. El modelo comienza con nodos m0. En cada paso de tiempo t se introduce un nuevo nodo, que está conectado a m de los nodos ya existentes. La probabilidad Pii de que el nuevo nodo está conectado al nodo i depende de la conectividad ki del nodo i tal que  _i = k _i/_jk _j. Para t grande la distribución de conectividad es una ley de potencia que sigue P(k) = 2 m²/k³..

La interconexión de una red se describe por su diámetro d, definido como la longitud media de los caminos más cortos entre dos nodos cualesquiera de la red. El diámetro caracteriza la habilidad de dos nodos para comunicarse entre sí: cuanto menor es d, más corta es la trayectoria esperada entre ellos. Las redes con un número muy grande de nodos pueden tener un diámetro bastante pequeño; Por ejemplo, el diámetro de la WWW con más de 800 millones de nodos20 es alrededor de 19 (ref.3), mientras que se cree que las redes sociales con más de seis mil millones de individuos tienen un diámetro de alrededor de seis21. Para comparar correctamente los dos modelos de red, hemos generado redes que tienen el mismo número de nodos y enlaces, de modo que P (k) sigue una distribución de Poisson para la red exponencial y una ley de potencia para la red libre de escala.

Para abordar la tolerancia de error de las redes, se estudian los cambios de diámetro cuando se elimina una pequeña fracción f de los nodos. El mal funcionamiento (ausencia) de cualquier nodo en general aumenta la distancia entre los nodos restantes, ya que puede eliminar algunos caminos que contribuyen a la interconexión del sistema. En efecto, para la red exponencial el diámetro aumenta monotónicamente con f (figura 2a); Así, a pesar de su cableado redundante (Fig. 1), es cada vez más difícil para los nodos restantes para comunicarse entre sí. Este comportamiento se basa en la homogeneidad de la red: puesto que todos los nodos tienen aproximadamente el mismo número de enlaces, todos ellos contribuyen igualmente al diámetro de la red, por lo que la eliminación de cada nodo causa la misma cantidad de daño. Por el contrario, observamos un comportamiento drásticamente diferente y sorprendente para la red libre de escala (figura 2a): el diámetro permanece sin cambios bajo un nivel creciente de errores. Así, incluso cuando el 5% de los nodos fallan, la comunicación entre los nodos restantes de la red no se ve afectada. Esta robustez de las redes libres de escala está enraizada en su distribución de conectividad extremadamente inhomogénea: debido a que la distribución de la ley de potencia implica que la mayoría de los nodos tienen sólo unos pocos enlaces, los nodos con conectividad pequeña serán seleccionados con mucha mayor probabilidad. La eliminación de estos nodos "pequeños" no altera la estructura de la ruta de los nodos restantes, y por lo tanto no tiene ningún impacto en la topología de red general.


(a) Comparación entre los modelos de red exponencial (E) y libre de escala (SF), cada uno de los cuales contiene N = 10.000 nodos y 20.000 enlaces (es decir, valla de cerca de valla izquierda = 4). Los símbolos azules corresponden al diámetro de las redes exponenciales (triángulos) y las redes libres de escala (cuadrados) cuando una fracción f de los nodos se elimina aleatoriamente (tolerancia de error). Los símbolos rojos muestran la respuesta de las redes exponenciales (diamantes) y las redes libres de escala (círculos) a los ataques, cuando se eliminan los nodos más conectados. Determinamos la dependencia f del diámetro para diferentes tamaños de sistema (N = 1.000; 5.000; 20.000) y encontramos que las curvas obtenidas, además de una corrección de tamaño logarítmico, se superponen con las mostradas en a, indicando que los resultados son independientes del Tamaño del sistema. Observamos que el diámetro de la red sin perturbaciones (f = 0) libre de escala es menor que el de la red exponencial, lo que indica que las redes libres de escala utilizan los enlaces disponibles para ellos de manera más eficiente, generando una red más interconectada. B, Los cambios en el diámetro de Internet bajo fallos aleatorios (cuadrados) o ataques (círculos). Utilizamos el mapa topológico de Internet, que contiene 6.209 nodos y 12.200 enlaces (k = 3.4), recopilados por el National Laboratory for Applied Network Research, cerca de la izquierda fencehttp: //moat.nlanr.net/Routing/rawdata/right fence. C, error (cuadrados) y ataque (círculos) de supervivencia de la World Wide Web, medido en una muestra que contiene 325.729 nodos y 1.498.353 enlaces3, de tal manera que k  = 4.59.

Un agente informado que intenta dañar deliberadamente una red no eliminará los nodos al azar, sino que preferentemente se dirigirá a los nodos más conectados. Para simular un ataque primero retiramos el nodo más conectado y continuamos seleccionando y eliminando nodos en orden decreciente de su conectividad k. Al medir el diámetro de una red exponencial bajo ataque, se observa que, debido a la homogeneidad de la red, no existe diferencia sustancial si los nodos se seleccionan aleatoriamente o en orden decreciente de conectividad (Figura 2a). Por otro lado, se observa un comportamiento drásticamente diferente para las redes libres de escala. Cuando se eliminan los nodos más conectados, el diámetro de la red libre de escala aumenta rápidamente, duplicando su valor original si se elimina el 5% de los nodos. Esta vulnerabilidad a los ataques está enraizada en la inhomogeneidad de la distribución de conectividad: la conectividad es mantenida por unos pocos nodos altamente conectados (Figura 1b), cuya eliminación altera drásticamente la topología de la red y disminuye la capacidad de los nodos restantes para comunicarse con cada uno otro.

Cuando los nodos se eliminan de una red, los clústeres de nodos cuyos vínculos con el sistema desaparecen pueden ser cortados (fragmentados) del clúster principal. Para entender mejor el impacto de los fallos y los ataques en la estructura de la red, investigamos a continuación este proceso de fragmentación. Medimos el tamaño del mayor grupo, S, que se muestra como una fracción del tamaño total del sistema, cuando una fracción f de los nodos se eliminan aleatoriamente o en un modo de ataque. Encontramos que para la red exponencial, a medida que aumentamos f, S muestra un comportamiento de tipo umbral tal que para f > f^e_c = 0.28 tenemos S  0. Se observa un comportamiento similar cuando se monitorea el tamaño medio de  s de los aislados (Es decir, todos los conglomerados excepto el más grande), encontrando que s aumenta rápidamente hasta que  s  2 en  f^e_c, después de lo cual disminuye   s = 1. Estos resultados indican el siguiente escenario de desglose ( Fig. 3a). Para los pequeños f, sólo los nodos individuales se separan, a  s  1, pero a medida que f aumenta, el tamaño de los fragmentos que caen del grupo principal aumenta, mostrando un comportamiento inusual en  f^e_c. Cuando el sistema se desmorona; El racimo principal se rompe en pedazos pequeños, llevando a S  0, y el tamaño de los fragmentos, valla cerrada a la izquierda, picos. A medida que continuamos eliminando los nodos (f > f^e_c ), fragmentamos estos grupos aislados, lo que conduce a una cerca decreciente de la cerca derecha. Debido a que el modelo ER es equivalente a la percolación dimensional infinita22, el comportamiento umbral observado es cualitativamente similar al punto crítico de percolación.



El tamaño relativo del mayor grupo S (símbolos abiertos) y el tamaño promedio de los grupos aislados dejó la valla cerrada (símbolos rellenos) en función de la fracción de nodos eliminados f para los mismos sistemas que en la Fig. 2. El tamaño S se define como la fracción de nodos contenidos en el grupo más grande (es decir, S = 1 para f = 0). A, Fragmentación de la red exponencial bajo fallos aleatorios (cuadrados) y ataques (círculos). B, Fragmentación de la red libre de escala bajo fallos aleatorios (cuadrados azules) y ataques (círculos rojos). El recuadro muestra las curvas de tolerancia de error para toda la gama de f, indicando que el racimo principal se descompone sólo después de haber sido completamente desinflado. Observamos que el comportamiento de la red libre de escala bajo errores es consistente con una transición de percolación extremadamente retardada: a tasas de error alto no realistas (f_max   0,75) observamos un pico muy pequeño en la valla de fencesright izquierda s ( s_max 1,06 ) Incluso en el caso de fallas aleatorias, lo que indica la existencia de un punto crítico. Para a y b se repitió el análisis para sistemas de tamaños N = 1.000, 5.000 y 20.000, encontrando que las curvas de cerca S y de valla izquierda superpuestas se superponen con la que se muestra aquí, indicando que el escenario de agrupamiento global y el valor de la Punto es independiente del tamaño del sistema. C, d, Fragmentación de Internet (c) y WWW (d), utilizando los datos topológicos descritos en la Fig. 2. Los símbolos son los mismos que en b. La valla de fencesright izquierda en d en el caso de ataque se muestra en una escala diferente, dibujada en el lado derecho del marco. Considerando que para f pequeño hemos dejado la cerca fencesright de la cerca 1.5, en fwc = 0.067 el tamaño medio del fragmento aumenta repentinamente, pico en   s _max   60, después decae rápidamente. Para la curva de ataque en d ordenamos los nodos en función del número de enlaces salientes, k_out. Observamos que mientras que las tres redes estudiadas, el modelo libre de escala, Internet y la WWW, tienen diferentes gamas, vallas de cerca y coeficientes de agrupamiento11, su respuesta a ataques y errores es idéntica. De hecho, encontramos que la diferencia entre estas magnitudes cambia sólo f_c  y la magnitud de d, S and s pero no la naturaleza de la respuesta de estas redes a las perturbaciones.

Sin embargo, la respuesta de una red libre de escala a los ataques y fallos es bastante diferente (Fig. 3b). Para los fracasos aleatorios no se observa un umbral para la fragmentación; En cambio, el tamaño del grupo más grande disminuye lentamente. El hecho de que  s  1 para la mayoría de los valores de f indica que la red es deflactada por los nodos que se rompen uno por uno, el nivel de error creciente que conduce al aislamiento de solo nodos solamente, no racimos de nodos. Por lo tanto, en contraste con la fragmentación catastrófica de la red exponencial en f^e _c, la red libre de escala permanece unida como un cluster grande para valores muy altos de f, proporcionando evidencia adicional de la estabilidad topológica de estas redes bajo fallos aleatorios. Este comportamiento es consistente con la existencia de un punto crítico extremadamente retrasado (Fig. 3) donde la red se descompone sólo después de que el racimo principal haya sido completamente desinflado. Por otra parte, la respuesta al ataque de la red libre de escala es similar (pero más rápida) a la respuesta al ataque y al fallo de la red exponencial (figura 3b): en un umbral crítico f^sf_c  0.18, menor que el valor  f^e_c  0.28  observado para la red exponencial, el sistema se deshace, formando muchos grupos aislados (Fig. 4).


a-f, La distribución de tamaños de clúster para varios valores de f cuando una red libre de escala de parámetros dada en la Fig. 3b está sujeto a fallos aleatorios (a-c) o ataques (d-f). Los paneles superiores, las redes exponenciales bajo fallos y ataques aleatorios y las redes libres de escala bajo ataques se comportan de manera similar. Para f pequeños, los grupos de diferentes tamaños se descomponen, aunque todavía hay un grupo grande. Esto es apoyado por la distribución de tamaño de clúster: aunque vemos algunos fragmentos de tamaños entre 1 y 16, hay un gran grupo de tamaño 9.000 (el tamaño del sistema original es 10.000). En un f_c crítico (ver Fig. 3) la red se rompe en fragmentos pequeños entre los tamaños 1 y 100 (b) y el grupo grande desaparece. A mayor aún f (c) los grupos se fragmentan más en nodos individuales o grupos de tamaño dos. Los paneles inferiores, las redes libres de escala siguen un escenario diferente bajo fallos aleatorios: el tamaño del grupo más grande disminuye lentamente como primeros nodos individuales, y luego se rompen grupos pequeños. De hecho, en f = 0,05 sólo los nodos simples y dobles se rompen (d). En f = 0.18, la red está fragmentada (b) bajo ataque, pero bajo fallas el gran grupo de tamaño 8.000 coexiste con grupos aislados de tamaños 1 a 5 (e). Incluso para una tasa de error de f = 0,45, el clúster grande persiste, el tamaño de los fragmentos rotos no excede 11 (f).


Aunque se están realizando grandes esfuerzos para diseñar componentes tolerantes a errores y de bajo rendimiento para los sistemas de comunicación, poco se sabe sobre el efecto de los errores y los ataques a la conectividad a gran escala de la red. A continuación, investigamos el error y la tolerancia de ataque de dos redes de creciente importancia económica y estratégica: Internet y la WWW.

Faloutsos et al.6 investigaron las propiedades topológicas de Internet en el nivel de enrutador e inter-dominio, encontrando que la distribución de conectividad sigue una ley de potencia,  P(k)  k^-2.48. En consecuencia, esperamos que debe mostrar la tolerancia de error y la vulnerabilidad de ataque predicho por nuestro estudio. Para probar esto, hemos utilizado la última encuesta de la topología de Internet, dando a la red en el nivel inter-dominio (sistema autónomo). De hecho, encontramos que el diámetro de Internet no se ve afectado por la eliminación aleatoria de hasta 2,5% de los nodos (un orden de magnitud mayor que la tasa de fallos (0,33%) de los enrutadores de Internet23), mientras que si el mismo porcentaje De los nodos más conectados son eliminados (ataque), d más que triples (figura 2b). De forma similar, el clúster grande conectado persiste para altas tasas de eliminación de nodos aleatorios, pero si los nodos se eliminan en el modo de ataque, el tamaño de los fragmentos que se rompen aumenta rápidamente, apareciendo el punto crítico a f^I_c  0.03 (Figura 3b).

La WWW forma un enorme grafo dirigido cuyos nodos son documentos y los bordes son los hipervínculos de URL que apuntan de un documento a otro, su topología determinando la capacidad de los motores de búsqueda para localizar información sobre él. La WWW es también una red libre de escala: las probabilidades Pout (k) y Pin (k) que un documento tiene k enlaces salientes y entrantes siguen una ley de poder sobre varios órdenes de magnitud, es decir, P(k)  k ^-, con _in = 2.1 y  _out = 2.45^3, 4, 24, Ya que no existe un mapa topológico completo de la WWW, limitamos nuestro estudio a un subconjunto de la red que contiene 325.729 nodos y 1.469.680 enlaces (k = 4.59 ) (Referencia 3). A pesar de la dirección de los enlaces, la respuesta del sistema es similar a las redes no dirigidas que investigamos anteriormente: después de un ligero incremento inicial, d permanece constante en el caso de fallas aleatorias y aumentos para ataques (Figura 2c). La red sobrevive como una agrupación grande bajo altas tasas de fracaso, pero el comportamiento de la cerca cercada por la izquierda indica que bajo ataque el sistema se desmorona abruptamente en f^w _c  = 0.067 (Figura 3c).

En resumen, encontramos que las redes libres de escala exhiben un sorprendentemente alto grado de tolerancia contra fallos aleatorios, una propiedad no compartida por sus contrapartes exponenciales. Esta robustez es probablemente la base de la tolerancia de error de muchos sistemas complejos, que van desde células8 a sistemas de comunicación distribuidos. También explica por qué, a pesar de los frecuentes problemas del enrutador23, rara vez experimentamos cortes de red globales o, a pesar de la indisponibilidad temporal de muchas páginas web, nuestra capacidad de navegar y localizar información en la web no se ve afectada. Sin embargo, la tolerancia de error se produce a expensas de la supervivencia de ataque: el diámetro de estas redes aumenta rápidamente y se rompen en muchos fragmentos aislados cuando se atacan los nodos más conectados. Esta disminución de la capacidad de supervivencia de los ataques es útil para el diseño de fármacos8, pero es menos alentadora para los sistemas de comunicación, como Internet o la WWW. Aunque generalmente se piensa que los ataques a redes con administración de recursos distribuidos son menos exitosos, nuestros resultados indican lo contrario. Las debilidades topológicas de las actuales redes de comunicación, enraizadas en su distribución de conectividad no homogénea, reducen seriamente su capacidad de supervivencia de ataque. Esto podría ser explotado por aquellos que buscan dañar estos sistemas.