Error and Attack Tolerance of Complex Networks

Este paper de Lászlo Barabási describe un comportamiento particular de las redes libres de escala que, años antes, definió formalmente (Emerge of Scaling in Random Networks). Basicamente las redes sin escala se caracterizan por seguir una distribución de tipo exponencial en términos de que los nodos dentro una red tienen una probabilidad P(k) de tener k enlaces y obedecen la siguiente relación:

 

Esta distribución tiene una curva de este tipo

p1Lo que implica que las redes libres de escala tengan distribuciones de este tipo es que mientras más enlaces tiene un nodo, decrece la probabilidad de que este exista dentro de la red. Es decir, habrá pocos nodos (hubs) con muchos enlaces y muchos nodos con pocos enlaces. Hay muchas redes y fenómenos que siguen este tipo de distribución en la vida real como por ejemplo

  • Internet
  • WWW
  • Distribución de la riqueza (Ley de Pareto)
  • Tamaño de las ciudades

Otra característica de estas redes libres de escala es que la probabilidad de que un nodo nuevo se conecte con otro cualquiera dentro de la red es

Donde Ki es la cantidad de enlaces que posee el nodo pre existente con el que se conectará el nuevo. Por lo que respeta lo que venimos observando sobre la formación de hubs ya que, mientras más enlaces tenga un nodo, mayor será la probabilidad que de uno nuevo se enlace con el.

Las redes que respetan las dos reglas que se definieron lucen como la figura debajo

scale-free-networkSe puede observar claramente la formación de hubs, o nodos con mayor cantidad de conexiones. Una imagen un poco mas atractiva que refleja la interconexión de internet y que mantiene una estructura similar

Internet_map_1024

Mapa parcial de Internet basado en la información obtenida del sitio opte.org en 2005. Cada línea entre dos nodos representa el enlace entre dos direcciones IP, y su longitud es proporcional al retardo entre estos.

Teniendo los conceptos básicos de las redes libres de escala ahora podemos adentrarnos en la lectura de este bello documento que habla sobre otras propiedades de las mismas. A saber, la tolerancia a fallos aleatorios y la debilidad a ataques específicos a nodos de tipo hubs que tienen estas redes.

Many complex systems display a surprising degree of tolerance against errors. For example, relatively simple organisms grow, persist and reproduce despite drastic pharmaceutical or enviromental interventions, an error tolerance attributed to the robustness of the underlying metabolic network. Complex communications display a surprising degree of robustness: Although key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these and other complex systems is often attributed  to the redundant wiring of the functional web defined by the systems components. Here we demostrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneously wired networks called scale-free networks, which include the World Wide Web (WWW), the internet, social networks, and cells. We find that such networks

 

Descargar: 200007-27_Nature-ErrorAttack

Fuentes:

  • http://es.wikipedia.org/wiki/Red_libre_de_escala
  • http://www.barabasilab.com

:wq!

 

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *