Design and implementation of metaheuristic algorithms for social network analysis

Resumen

En una sociedad donde la instantaneidad está cada vez más establecida, existe una necesidad de obtener soluciones a problemas del mundo real de una forma rápida y precisa. Con respecto a la precisión, o más específicamente la optimalidad, la disciplina científica que lidia con este problema es la optimización. Este área del conocimiento puede verse como un punto de encuentro entre varias disciplinas, como la investigación operativa, la estadística, la informática o la inteligencia artificial. Existe una gran cantidad de problemas interesantes de la vida real que pueden ser abordados desde el punto de vista de la optimización: calcular la ruta más corta para ir de casa al trabajo, encontrar la mejor manera para colocar el máximo número de contenedores en un barco para enviar productos alrededor del mundo o saber cuáles son los puntos más débiles de una red de ordenadores para dedicar más recursos en su protección. Todos estos problemas pueden ser resueltos de dos maneras princpales: a través de algoritmos exactos o de algoritmos aproximados. El principal problema al que se enfrentan los algoritmos exactos es que, cuando el espacio de soluciones a explorar es muy amplio, el tiempo de cómputo requerido para proporcionar una solución óptima al problema es inasumible. En este contexto, los algoritmos aproximados emergen como una alternativa, con la principal desventaja de que no garantizan alcanzar una solución óptima global. Sin embargo, si se selecciona la técnica adecuada, una solución de alta calidad puede garantizarse. Este es el caso de los algoritmos heurísticos. El Problema de Detección de Comunidades (CDP) es un problema NP-difícil que pertenece a la familia de problemas del Análisis de Redes Sociales (SNA). El principal objetivo en el CDP es agrupar usuarios dentro de una red social dependiendo de sus características, sus relaciones y otras propiedades de la red en sí misma. Se dice que una buena solucioón para el CDP se caracteriza por una buena estructura de comunidad. La estructura de comunidad se considera buena cuando los grupos resultantes contienen nodos altamente conectados entre sí y escasamente conectados hacia nodos pertenecientes a otros grupos. Existen diferentes variantes del mismo problema en los que se consideran diferentes restricciones. Por ejemplo, el número de comunidades que contiene una solución es fijada a priori, o los nodos pueden ser asignados a diferentes grupos simultáneamente. El problema también se puede afrontar optimizando diferentes funciones objetivo, y teniendo en cuenta un único o múltiples objetivos. A pesar de todo lo anterior, el objetivo último siempre es el mismo: obtener soluciones que presentan una buena estructura de comunidad. En esta Tesis Doctoral se proponen diferentes algoritmos heurísticos para resolver diferentes variantes del CDP. Se aplican diferentes metodologías, como la búsqueda de vecindad variable (VNS), Iterated Greedy (IG), o la búsqueda dispersa (SS). Cada propuesta se ha evaluado tanto contra redes sintéticas como del mundo real, para comprobar su utilidad y aplicación en estos contextos. Los resultados obtenidos superan las propuestas del estado del arte en todas las variantes del CDP estudiadas.