Nuevo algoritmo para atacar redes (criminales) basado en abejas

Los científicos desarrollan un nuevo algoritmo inspirado en colonias de abejas para ayudar a desmantelar redes sociales criminales
Phys.org



 Los científicos desarrollan un nuevo algoritmo inspirado en colonias de abejas para ayudar a desmantelar redes sociales criminales

Investigadores de la Universidad de Granada (UGR) han diseñado un algoritmo, inspirado en el comportamiento inteligente y social de las colonias de abejas, que permite a las fuerzas del orden atacar y desmantelar cualquier tipo de red social que suponga una amenaza, ya sean redes sociales físicas o virtuales vinculadas al crimen organizado y al terrorismo yihadista.

Las posibles aplicaciones de este nuevo algoritmo bio-inspirado, que ayuda a tomar decisiones óptimas para desmantelar cualquier tipo de red social, son muchas y variadas: desde desmantelar una red criminal hasta facilitar el diseño de estrategias de vacunación capaces de contener la difusión de una pandemia.
La herramienta diseñada por los investigadores de la UGR detecta e identifica automáticamente a los actores o nodos más peligrosos dentro de una determinada red social y la densidad de las relaciones interconectadas entre ellos, lo que puede ayudar a las autoridades a tomar sus decisiones y actuar de la manera más eficiente posible.
Según lo explicado por uno de los autores de este artículo, Manuel Lozano Márquez, del Departamento de Informática e Inteligencia Artificial de la UGR, "las abejas forman sociedades bastante bien organizadas, en las que cada miembro tiene un papel específico. : Las abejas exploradoras que buscan fuentes de alimento, las abejas obreras que recolectan alimentos y las abejas supervisoras que esperan en la colonia ".
El intercambio de datos y los procesos de comunicación se establecen entre esas tres funciones, lo que hace que el rendimiento general de la colonia sea muy rentable. Los científicos de la UGR han simulado este comportamiento utilizando abejas in silico con el fin de encontrar estrategias efectivas y eficientes para desmantelar redes. Los resultados de los experimentos indican que la técnica propuesta mejora significativamente, desde un punto de vista estadístico, la estrategia clásica utilizada para atacar y desmantelar las redes sociales.

Redes sociales

Muchos sistemas complejos de interacción relacionados con la naturaleza y relacionados con la humanidad están estructurados en una red compleja, es decir, están formados por una serie de actores interrelacionados. Las redes sociales son un ejemplo muy reciente de esto. Algunas redes son perniciosas debido a su potencial para causar daño a las personas, las infraestructuras críticas y los intereses económicos.
El método clásico (y también el más natural e intuitivo) para desmantelar una red es identificar a sus principales actores y actuar sobre ellos. Sin embargo, esta estrategia no garantiza que la red resultante esté totalmente desprovista de poder organizativo y reconstructivo, y puede seguir causando daño.

"Para encontrar la forma más efectiva de desmantelar una red es necesario desarrollar y poner en marcha un proceso de optimización que analiza una multitud de situaciones y selecciona la mejor opción en el menor tiempo posible Es similar a lo que un programa de ajedrez Lo hace al identificar, predecir y comprobar los posibles pasos o caminos que pueden ocurrir en un juego de ajedrez a partir de un momento dado y el movimiento ", dice Humberto Trujillo Mendoza del Departamento de Metodología de las Ciencias del Comportamiento de la UGR y uno de los autores de la papel.

Como explican los autores, "la sutileza con que grupos o colonias de seres vivos relativamente simples (hormigas, termitas, abejas, etc.) son capaces de resolver problemas vitales para sobrevivir es una prueba de la eficacia de la evolución". A través de ciertas interrelaciones entre los miembros de una colonia, surge un comportamiento colectivo de esa colonia, que les permite reaccionar de manera eficiente a situaciones ambientales problemáticas. Esa tarea, aplicada por la UGR al campo de la inteligencia artificial, sería imposible de realizar por los miembros individuales de la colonia.

En la actualidad, este grupo de investigación está trabajando en el desarrollo de otros algoritmos similares a los descritos. Esta vez lo están haciendo para determinar los nodos de la red social a los que deben conectarse ciertos "infiltrados" para aumentar la cantidad y calidad de la información recopilada para mejorar el conocimiento de las relaciones entre los otros actores, optimizando así al desmantelamiento de la red.

La literatura sobre los ataques de red

La mayor parte de la investigación sobre los ataques de red se basa en la idea de nodos críticos, lo que permite caracterizar la vulnerabilidad y robustez de una determinada red con respecto a la remoción de nodos, causada por vallas adversarias, fallas aleatorias o desastres naturales. Esta clase de problemas, CNP, ha sido ampliamente estudiada en la última década (Walteros y Pardalos, 2012), y diferentes casos han sido analizados según los intereses particulares.
Arulselvan et al. (2009) y Pullan (2015) se centraron en la minimización del número total de pares de vértices conectados. Shen et al. (2012) con el objetivo de maximizar el número de componentes conectados y minimizar el tamaño del más grande. Ortiz-Arroyo (2010) trabajó en la maximización de la entropía de información gráfica. Veremyev et al. (2015) analizaron la minimización de una medida de conectividad basada en la distancia, como la eficiencia gráfica, el índice de Harary, la longitud de la trayectoria característica y la cercanía residual. Gunasekara et al. (2015) también abordaron casos CNP multiobjetivos que enfatizaron la maximización de la centralidad del vector propio medio y la distancia entre nodos críticos.
Sin embargo, la mayor parte de la atención en la literatura CNP se ha centrado en el caso particular definido por Arulselvan et al. (2009), donde el ataque óptimo fragmenta al máximo la red y simultáneamente minimiza la varianza entre el número de vértices en los componentes conectados resultantes. Es decir, la red residual contiene un conjunto relativamente grande de componentes conectados, cada uno con un número similar de vértices (Ventresca y Aleman, 2015a). Esta instancia CNP se referenciará como CNP-A. Arulsel van et al. (2009) presentó un modelo de programación lineal entera (ILP) y un enfoque heurístico basado en un algoritmo codicioso acoplado con una fase de búsqueda local para el CNP-A. Posteriormente, la naturaleza NP-completa de este problema (Arulselvan et al., 2009) promovió la aplicación de metaheurísticas para obtener soluciones casi óptimas dentro de tiempos computacionales razonables: Ventresca (2012) propuso un modelo de aprendizaje incremental basado en población y un apareamiento simulado, Pullan (2015) diseñó un algoritmo codicioso de varios arranques, y Aringhieri et al. (2015) presentó un enfoque de búsqueda de vecindario variable.
Los ataques basados ​​en la centralidad (Crucitti et al., 2004, Iyer et al., 2013) son otra alternativa para abordar CNPs, que apuntan a los vértices a ser removidos de acuerdo a una medida de centralidad dada y una de las siguientes estrategias:

• En ataques simultáneos dirigidos, la medida de centralidad se calcula para todos los vértices de la red, y los k con los valores más altos se eliminan a la vez.
• En los ataques segmentados secuenciales, sólo el vértice con la medida de centralidad más alta se elimina a la vez y el proceso se repite k veces. Dado que cada remoción probablemente modifica los valores de centralidad de los vértices restantes, la métrica se calcula una vez para el gráfico inicial y de nuevo después de cada eliminación para los vértices restantes.

Iyer et al. (2013) investigaron el efecto de los ataques basados ​​en la centralidad con diferentes esquemas de remoción y medidas de centralidad, como el grado, BC, la cercanía y el autovector en una amplia gama de redes.
Encontraron que la eliminación secuencial del vértice con BC más alto era el método más efectivo para degradar la estructura de la red. Esta conclusión también fue apoyada por Ventresca y Aleman (2015b), quienes analizaron los efectos de acuerdo a seis métricas de centralidad.

Referencias

• Aringhieri, R., Grosso, A., Hosteins, P., Scatamacchia, R., 2015. VNS solutions for the critical node problem. Electronic Notes in Discrete Mathematics 47, 37–44.
• Arulselvan, A., Commander, C. W., Elefteriadou, L., Pardalos, P. M., 2009. Detecting critical nodes in sparse graphs. Computers & Operations Research 36 (7), 2193–2200.
• Crucitti, P., Latora, V., Marchiori, M., Rapisarda, A., 2004. Error and attack tolerance of complex networks. Physica A: Statistical Mechanics and its Applications 340 (1), 388–394
• Iyer, S., Timothy, K., Bala, S., Zhen, W., 04 2013. Attack robustness and centrality of complex networks. PLoS ONE 8 (4), e59613.
• Ortiz-Arroyo, D., 2010. Computational Social Network Analysis: Trends, Tools and Research Advances. Springer London, London, Ch. Discovering sets of key players in social networks, pp. 27–47.
• Pullan, W., 2015. Heuristic identification of critical nodes in sparse real-world graphs. Journal of Heuristics 21 (5), 577–598.
• Shen, S., Smith, J. C., Goli, R., 2012. Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization 9 (3), 172–188.
• Ventresca, M., Aleman, D., 2014. A derandomized approximation algorithm for the critical node detection problem. Computers & Operations Research 43, 261–270.
• Veremyev, A., Prokopyev, O. A., Pasiliao, E. L., 2015. Critical nodes for distance-based connectivity and related problems in graphs. Networks 66 (3), 170–195.
• Walteros, J. L., Pardalos, P. M., 2012. Applications of Mathematics and Informatics in Military Science. Springer New York, New York, NY, Ch. Selected topics in critical element detection, pp. 9–26.

Más información: Manuel Lozano et al. Optimizing network attacks by artificial bee colony, Information Sciences (2017). DOI: 10.1016/j.ins.2016.10.014