Design and Implementation of Metaheuristic Algorithms for Social Network Analysis

Abstract

En los últimos años, el volumen de datos e información que se maneja en el mundo ha crecido de forma exponencial, especialmente desde la aparición de Internet y la digitalización de los procesos. Realizar una compra, mantener una reunión de trabajo o, simplemente, relacionarse, son acciones que hoy en día encuentran un complemento (si no un sustituto total) en las tecnologías. Este hecho tiene una vertiente que merece la pena atender: a mayor volumen de información, más eficientes han de ser los procesos que la recogen, procesan y convierten en información útil. La optimización combinatoria cobra un papel fundamental en este tipo de procesos. Existe una gran cantidad de problemas interesantes del mundo real que pueden abordarse desde el punto de vista de la optimización: calcular la ruta más corta (o la más ecológica) para ir de un lugar a otro; encontrar la mejor manera para colocar mercancías en un barco para su transporte a lo largo del mundo; saber cuáles son los puntos más débiles en una red de ordenadores para dedicar más recursos a su protección; o establecer relaciones entre usuarios de una determinada red social, de forma que seamos capaces de agruparlos y detectar patrones de comportamiento, problemas de salud mental o, incluso, detectar radicalismos. Todos estos problemas se pueden abordar, principalmente, de dos maneras: mediante algoritmos exactos o a través de algoritmos aproximados. La principal desventaja que nos encontramos a la hora de utilizar algoritmos exactos es que, cuando el espacio de soluciones a explorar comienza a crecer, el tiempo de cómputo requerido para obtener la solución óptima tiende a ser inasumible. En este contexto, se nos presenta una alternativa: los algoritmos aproximados. Su principal desventaja es que no garantizan alcanzar una solución óptima global. Sin embargo, seleccionando una técnica adecuada, se puede garantizar la obtención de una solución de alta calidad, que en muchas ocasiones es suficiente para el problema que estamos abordando. Este es el caso de los algoritmos heurísticos. Esta tesis doctoral se centra en resolver diferentes variantes del Problema de Detección de Comunidades (PDC), un problema NP-difícil perteneciente a la familia de problemas del Análisis de Redes Sociales (ARS). El principal objetivo del PDC es agrupar usuarios dentro de una red social basándose en sus características, sus relaciones y otras propiedades de la red en sí misma. Se dice que una buena solución para el PDC se caracteriza por tener una buena estructura de comunidad. La estructura de comunidad se considera buena cuando los grupos resultantes contienen usuarios altamente relacionados entre sí y escasamente relacionados con usuarios pertenecientes a otros grupos. Existen diferentes variantes del problema en los que se consideran diferentes restricciones. Por ejemplo, un usuario podría pertenecer simultáneamente a varias comunidades diferentes, situación que se aproxima más a las casuísticas del mundo real. El problema también podría abordarse teniendo en cuenta un solo objetivo, o responder a múltiples objetivos (incluso opuestos entre sí). Sin embargo, la aportación más relevante de esta tesis doctoral es que todos los algoritmos desarrollados son fácilmente adaptables para resolver diferentes problemas de optimización combinatoria, no sólo aquellos relacionados con el análisis de redes sociales o la detección de comunidades.