Optimización de ataques a redes complejas mediante un algoritmo de colonias de abejas artificiales

Abstract

En los últimos años, ha crecido el interés en formular como un problema de optimización la tarea de concebir ataques efectivos que causen el máximo daño sobre redes complejas. En este caso, los ataques se modelan como un proceso de eliminación de k vértices del grafo que representa la red. En este trabajo, seguimos esta línea de investigación presentando un problema de optimización que concierne la selección de los nodos a eliminar con el objetivo de minimizar el máximo valor de intermediación en el grafo residual. La intermediación es una medida de centralidad bien conocida que evalúa la importancia de los nodos de la red de acuerdo a su participación en los caminos más cortos. La relevancia de este indicador dentro de la tecnología actual disponible para el análisis de redes nos ha llevado a plantear esta técnica para planificar ataques efectivos sobre redes. Además, para abordar el problema de optimización, proponemos un algoritmo de colonias de abejas artificiales, que es una técnica de inteligencia colectiva inspirada en el comportamiento de las abejas cuando realizan la búsqueda de comida. Nuestra propuesta explota el conocimiento útil sobre el problema que se obtiene de la exploración de las fuentes de comida, aplicando una destrucción parcial de las soluciones escogidas y una reconstrucción heurística de las mismas. Mediante el análisis experimental de los resultados mostramos el buen comportamiento del algoritmo propuesto, con respecto a métodos de la literatura que pueden adoptarse para enfrentarse con el problema, tal como el método de ataque secuencial basado en centralidad.