20 años del paper de Watts y Strogatz

Veinte años de ciencia de redes

La idea de que todos en el mundo están conectados con todos los demás por solo seis grados de separación fue explicada por el modelo de red del 'mundo pequeño' hace 20 años. Lo que parecía ser un hallazgo de nicho resultó tener enormes consecuencias.

Alessandro Vespignani | Nature
Nature 558, 528-529 (2018)
doi: 10.1038/d41586-018-05444-y

En 1998, Watts y Strogatz[1] introdujeron el modelo de redes de "mundo pequeño", que describe la agrupación y las breves separaciones de nodos que se encuentran en muchas redes de la vida real. Aún recuerdo vívidamente la discusión que tuve con mis colegas físicos estadísticos en ese momento: el modelo fue visto como algo interesante, pero parecía ser simplemente una salida exótica de las estructuras de red regulares, parecidas a grillas, a las que estábamos acostumbrados. Pero cuanto más asimilados fueron los científicos de diferentes campos, más evidente fue su profunda implicación para nuestra comprensión del comportamiento dinámico y las transiciones de fase en fenómenos del mundo real que van desde los procesos de contagio a la difusión de la información. Pronto se hizo evidente que el documento había iniciado una nueva era de investigación que conduciría al establecimiento de la ciencia de redes como un campo multidisciplinario.

Antes de que Watts y Strogatz publicaran su artículo, los algoritmos arquetípicos de generación de redes se basaban en procesos de construcción como los descritos por el modelo Erdös-Rényi[2]. Estos procesos se caracterizan por una falta de conocimiento de los principios que guían la creación de conexiones (enlaces) entre los nodos en las redes, y hacen la suposición simple de que los pares de nodos se pueden conectar al azar con una probabilidad de conexión dada. Tal proceso genera redes aleatorias, en las que la longitud de camino promedio entre dos nodos cualquiera de la red, medida como el menor número de aristas necesarias para conectar los nodos, se escala como el logaritmo del número total de nodos. En otras palabras, la aleatoriedad es suficiente para explicar el fenómeno del mundo pequeño popularizado como "seis grados de separación" 3,4: la idea de que todos en el mundo están conectados con todos los demás a través de una cadena de, como máximo, seis conocidos mutuos.

Sin embargo, la construcción aleatoria no alcanzó a capturar el carácter local de los nodos observados en las redes del mundo real. La exclusividad se mide cuantitativamente mediante el coeficiente de agrupamiento de un nodo, que se define como la relación entre el número de enlaces entre los vecinos de un nodo y el número máximo de dichos enlaces. En las redes del mundo real, la agrupación de nodos se ejemplifica claramente con el axioma "los amigos de mis amigos son mis amigos": la probabilidad de que tres personas sean amigos entre sí en una red social, por ejemplo, es generalmente mucho más alta de lo que sería predicho por una red modelo construida usando el proceso simple y estocástico.

Para superar la dicotomía entre aleatoriedad y clichishness, Watts y Strogatz propusieron un modelo cuyo punto de partida es una red regular que tiene un gran coeficiente de agrupamiento. La estocasticidad se introduce luego al permitir que los enlaces se vuelvan a cablear al azar entre los nodos, con una probabilidad fija de recableado (p) para todos los enlaces. Al sintonizar p, el modelo interpola efectivamente entre una red regular (p → 0) y una red completamente aleatoria (p → 1).

En valores de p muy pequeños, la red resultante es una retícula regular y, por lo tanto, tiene un alto coeficiente de agrupamiento. Sin embargo, incluso a una p pequeña, aparecen atajos entre los nodos distantes de la red, lo que reduce drásticamente la longitud promedio del camino más corto (Fig. 1). Watts y Strogatz demostraron que, dependiendo del número de nodos5, es posible encontrar redes que tengan un gran coeficiente de agrupamiento y distancias medias cortas entre nodos para una amplia gama de valores p, reconciliando así el fenómeno del mundo pequeño con el carácter complejo de la red.




Figura 1 | El modelo de red de mundo pequeño. En 1998, Watts y Strogatz1 describieron un modelo que ayuda a explicar las estructuras de las redes en el mundo real. a. Comenzaron con una red regular, representada aquí como nodos conectados en una red triangular en la que cada nodo está conectado a otros seis nodos. b. Luego permitieron que los enlaces entre nodos se reconectaran al azar, con una probabilidad fija de volver a cablear todos los enlaces. A medida que aumenta la probabilidad, un número creciente de atajos (líneas rojas) conecta nodos distantes en la red. Esto genera el efecto del mundo pequeño: todos los nodos de la red se pueden conectar pasando a lo largo de una pequeña cantidad de enlaces entre nodos, pero los nodos vecinos se conectan entre sí, formando camarillas agrupadas.


El modelo de Watts y Strogatz fue inicialmente considerado simplemente como la explicación de seis grados de separación. Pero posiblemente su impacto más importante fue allanar el camino para estudios sobre el efecto de la estructura de red en una amplia gama de fenómenos dinámicos. Otro documento fue también fundamental: en 1999, Barabási y Albert propusieron el modelo de red de "acoplamiento preferencial" 6, que destacó que la distribución de probabilidad que describe el número de conexiones que se forman entre los nodos en las redes reales a menudo se caracteriza por "cola pesada". 'distribuciones, en lugar de la distribución de Poisson predicha por redes aleatorias. El amplio espectro de comportamientos emergentes y transiciones de fase encapsuladas en redes que tienen conectividad agrupada (como en el modelo de Watts y Strogatz) y una conexión heterogénea (como en el modelo de conexión preferencial) atrajeron la atención de científicos de muchos campos.

Siguieron una serie de descubrimientos, destacando cómo la compleja estructura de tales redes sustenta los sistemas del mundo real, con implicaciones para la robustez de la red, la propagación de epidemias, el flujo de información y la sincronización del comportamiento colectivo a través de las redes7,8. Por ejemplo, el patrón de conectividad del mundo pequeño demostró ser la clave para comprender la estructura de la World Wide Web9 y cómo las áreas anatómicas y funcionales del cerebro se comunican entre sí10. Otras propiedades estructurales de las redes se analizaron poco después del 11-13, como la modularidad y el concepto de motivos estructurales, que ayudaron a los científicos a caracterizar y comprender la arquitectura de sistemas vivos y artificiales, desde redes subcelulares hasta ecosistemas e Internet.

La generación actual de investigación en red fertiliza áreas que se benefician de una potencia de cómputo sin precedentes, grandes conjuntos de datos y nuevas técnicas de modelado computacional, y así proporciona un puente entre la dinámica de los nodos individuales y las propiedades emergentes de las redes macroscópicas. Pero la inmediatez y la simplicidad de los modelos de pequeño tamaño y de conexión preferencial todavía sustentan nuestra comprensión de la topología de red. De hecho, la relevancia de estos modelos para diferentes áreas de la ciencia sentó las bases del campo multidisciplinario ahora conocido como ciencia de redes.

Integrar conocimientos y metodologías de campos tan dispares como las ciencias sociales, la física, la biología, la informática y las matemáticas aplicadas no fue fácil. Tomó varios años encontrar un terreno común, acordar definiciones y conciliar y apreciar los diferentes enfoques que cada campo había adoptado para estudiar redes. Este es todavía un trabajo en progreso, que presenta todas las dificultades y trampas inherentes al trabajo interdisciplinario. Sin embargo, en los últimos 20 años ha surgido una vibrante comunidad de ciencia de redes, con sus propias prestigiosas revistas, institutos de investigación y conferencias a las que asistieron miles de científicos.

En el vigésimo aniversario del documento, más de 18,000 documentos han citado el modelo, que ahora se considera una de las topologías de red de referencia. Watts y Strogatz cerraron su periódico diciendo: "Esperamos que nuestro trabajo estimule más estudios de las redes del mundo pequeño". Tal vez ninguna afirmación haya sido nunca más profética.

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.