István Kovács A. y Lászlo Barabási
Nature 524, 38-39 (06 de agosto 2015) doi: 10.1038/524038a
Publicado en Internet el 05 de agosto 2015
Señalando los nodos cuya eliminación más eficaz perturba una red se ha vuelto mucho más fácil con el desarrollo de un algoritmo eficiente. Las aplicaciones potenciales podrían incluir la ciberseguridad y el control de enfermedades. Ver Letter p.65
Una verdad perdurable de la ciencia de la red es que la eliminación de unos pocos nodos altamente conectados, o concentradores, puede romper una red compleja en muchos componentes (1) desconectado. A veces, una red fragmentada e inactivo es más deseable que un funcionamiento una. Consideremos, por ejemplo, la necesidad de eliminar las bacterias mediante la interrupción de su red molecular o mediante la vacunación de unos pocos individuos en una población para romper la red de contacto a través del cual se extiende un patógeno. En una búsqueda para encontrar las balas de plata que pueden desmantelar efectivamente las redes grandes, Morone y Makse (2) (página 65 de esta edición) han desarrollado un algoritmo que logra esto mediante la identificación de conjuntos de nodos de red conocidos como factores de influencia.
No está claro si la focalización y la eliminación de centros de la red - definido como los nodos con el mayor número de enlaces - puede infligir el máximo interrupción en una red. Puede ser más eficaz para eliminar una combinación de hubs y central, pero, bien comunicado menos, los nodos. La eliminación de los centros se prefiere generalmente porque son fáciles de localizar, mientras que identifica el conjunto óptimo de nodos en los que la eliminación causaría un daño máximo es un problema en tiempo polinomial no determinista (NP-hard) (3). Esto significa que es computacionalmente factible sólo para redes pequeñas. Morone y Makse atacan el problema de la interrupción de la red mediante la asignación de la integridad de una red aleatoria en forma de árbol en teoría de la percolación óptima (4,5). A partir de esto, se derivan una función de energía con un mínimo que se corresponde con el conjunto de nodos que deben ser eliminados, para producir una red cuyo grupo más grande es tan pequeño como sea posible. Aunque la identificación de este mínimo es todavía un problema NP-hard, los autores se inspiraron en la forma de la función de energía para encontrar un algoritmo simple que ofrece una solución aproximada.
Para ello, Morone y Makse introducen el concepto de influencia colectiva, que es el producto de grado del nodo reducida (el número de sus enlaces menos uno) y la suma de los reducidos grados de los nodos que son un cierto número de pasos de él (Fig. 1). Influencia colectiva describe cuántos otros nodos se puede llegar desde un nodo dado, en el supuesto de que los nodos de alta influencia colectiva tienen un papel crucial en la red. El algoritmo basado colectiva-influencia, entonces elimina secuencialmente nodos, empezando por los que tienen la mayor influencia colectiva (conocidos como factores de influencia) y volver a calcular la influencia colectiva del resto después de cada operación. Los autores muestran que, para grandes redes, retirar el conjunto de factores de influencia identificados por este algoritmo es más eficaz en la fragmentación de una red de eliminar los cubos, o que la eliminación de nodos que se identifican a través de otros algoritmos, tales como centralidad de PageRank (6) o cercanía (7). El conjunto de factores de influencia identificados por los autores contiene muchos nodos con pocas conexiones. Esto pone de relieve el hecho de que la importancia de un nodo para garantizar la integridad de la red está determinada no sólo por el número de enlaces directos que tiene para otros nodos, sino también por los que otros nodos que está conectado.
Figura 1: demolición de red óptima.
Demolición óptima de red.
Morone y Makse (2) introducen un algoritmo que les permite desmantelar de manera eficiente las redes. Los autores definen la influencia colectiva de un nodo de red como el producto de su grado reducido (el número de sus conexiones más cercanas, k, menos uno), y total reducido el grado de todos los nodos a una distancia d de la misma (que se define como el número de a unos pasos de ella). a, En esta red, para d = 2, el nodo rojo con k = 4 tiene la mayor influencia colectiva, porque total reducido el grado de los nodos en d = 2 de la misma (verde y círculos de color amarillo) es de 21. Esto produce una influencia colectiva de 3 × 21 = 63. El cubo más conectada, con k = 6 (círculo amarillo), tiene una influencia colectiva de 60. b, Quitar los 6 nodos con el mayor k (círculos blancos) causa un daño considerable a la red , pero deja una sub-red que contiene 12 nodos no perturbadas. c, Por el contrario, el algoritmo desarrollado por los autores les permite identificar un conjunto de nodos (conocido como influenciadores) en función de su influencia colectiva. El uso de este, la eliminación de cuatro nodos factor de influencia (círculos blancos) se traduce en una red fragmentada en que el clúster conectado más grande que permanece tiene sólo diez nodos. Esto ilustra la eficacia del algoritmo sobre los métodos convencionales para dar prioridad a la destrucción de la red.
El algoritmo de influencia colectiva es notable por su complejidad computacional, ya que sólo requiere cálculos N2logN para desmantelar una red que contiene un número N de nodos. Su complejidad se reduce a NlogN si, en lugar de nodos individuales, una fracción fija del total se elimina en cada paso de la computación. Los autores comparan su método a las predicciones de la teoría spin-glass, que fue desarrollado originalmente para describir las propiedades de los imanes desordenados y ha encontrado una amplia gama de aplicaciones en el análisis de redes. Concluyen que los nodos priorizados por el algoritmo colectiva-influencia representan una solución aproximada, que tiene un tamaño similar a la de la solución óptima teórica. Sobre la base de la teoría de spin-vidrio, podemos esperar que la solución colectiva influencia tiene sólo una pequeña superposición con la solución óptima, y por lo tanto deben ser tratados con precaución. Sin embargo, los factores de influencia encontrados por influencia colectiva son más eficaces en la destrucción de una red de nodos seleccionados por otros métodos. Así que, aunque el método colectivo-influencia es aproximada, es más rápido y más eficiente.
Como con cualquier nuevo algoritmo, preguntas abiertas abundan. El algoritmo de influencia colectiva tiene un solo parámetro libre - la distancia, expresada en el número de pasos, desde cualquier nodo dado. En distancia cero, la influencia colectiva de un nodo es igual al cuadrado de su grado reducido, y por lo tanto en este caso el algoritmo simplemente elimina los cubos. Para mejorar la precisión del algoritmo, uno debe elegir una distancia distinta de cero - pero uno que no es demasiado grande, ya que para grandes distancias se alcanzan los límites de la red, disminuyendo influencia colectiva de un nodo (la influencia colectiva se aproxima a cero). Aunque Morone y Makse encuentran que cualquier distancia mayor que uno trabaja, un criterio firme para la elección de un valor óptimo es deficiente y que sería deseable. Por último, debido a que los autores diseñaron su algoritmo para trabajar en redes que son localmente más trabajo y pruebas cuantitativas son necesarias en su precisión esperada para redes con bucles, como árbol, tales como la mayoría de las redes sociales.
El algoritmo de influencia colectiva, al igual que los algoritmos similares, elimina un nodo junto con todos sus enlaces. Sin embargo, para muchos sistemas, la extirpación de ganglios es demasiado drástico una intervención. Toques más suaves, como la eliminación o recableado de enlaces específicos, son más manejables y deseables. Por ejemplo, estos enfoques son relevantes para las redes en las células biológicas, en el que muchas enfermedades son causadas por mutaciones que resultan en la supresión de enlaces en lugar de la eliminación completa de nodos (8). La comprensión de los efectos tales "referidos a enlaces", y el diseño de algoritmos que pueden detectar el número mínimo de enlaces eliminar a fin de lograr un resultado determinado, sigue siendo un reto para el trabajo futuro.
La identificación de factores de influencia óptimos, ya sea a nivel del nodo o de enlace, es el primer paso hacia la construcción de redes que podrían ser robusto frente a ambos ataques y fracasos. Dominar los principios de diseño de este tipo de redes super robustas podría tener profundas implicaciones para cualquier cosa, desde la seguridad cibernética para el diseño de una red de energía ataque- y tolerante a errores, y puede incluso nos permitirá desarrollar fármacos que puedan rescatar a una red celular de su estado de enfermedad con efectos secundarios mínimos.
Referencias
- Albert, R., Jeong, H. & Barabási, A.-L. Nature 406, 378–382 (2000).
- Morone, F. & Makse, H. A. Nature 524, 65–68 (2015).
- Garey, M. R. & Johnson, D. S. in Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, 1979).
- Hashimoto, K. Adv. Stud. Pure Math. 15, 211–280 (1989).
- Karrer, B., Newman, M. E. J. & Zdeborová, L. Phys. Rev. Lett. 113, 208702 (2014).
- Brin, S. & Page, L. Proc. 7th Int. World Wide Web Conf. 30, 107–117 (1998).
- Freeman, L. C. Soc. Networks 1, 215–239 (1978–79).
- Sahni, N. et al. Cell 161, 647–660 (2015).
