Algoritmos bio-inspirados para la detección de comunidades dinámicas en redes complejas

• Autores: Ángel Panizo Lledot
• Directores de la Tesis: David Camacho Fernández (dir. tes.) , Gema Bello Orgaz (codir. tes.) , Manuel Sánchez-Montañés Isla (tut. tes.)
• Lectura: En la Universidad Autónoma de Madrid ( España ) en 2022
• Idioma: español
• Número de páginas: 223
• Tribunal Calificador de la Tesis: Sancho Salcedo Sanz (presid.) , Álvaro Ortigosa (secret.) , Ricardo Aler Mur (voc.) , Cristian Oliver Ramírez Atencia (voc.) , Alejandro Martín García (voc.)
• Enlaces
  • Tesis en acceso abierto en: Biblos-e Archivo
• Resumen

  • Esta tesis se centra en el desarrollo de algoritmos meta-heurísticos poblacionales eficientes aplicables a dominios de redes dinámicas, es decir, que evolucionan en el tiempo. Específicamente, en el desarrollo de Algoritmos Genéticos (GAs) eficientes para la detección de comunidades dinámicas. En pocas palabras, podemos considerar al problema de detección de comunidades (PDC) como el proceso de hacer "clustering" sobre redes, es decir, dada una red compuesta por nodos o entidades y aristas o conexiones entre estas entidades, el PCD consiste en hacer grupos de nodos de tal manera que los miembros de un mismo grupo contenga más conexiones entre ellos que entre el resto de nodos de la red.

    Las meta-heurísticas bio-inspiradas ofrecen un compromiso excelente entre potencia, flexibilidad y escalabilidad. Su mejor ventaja es que son capaces de generar soluciones con una calidad aceptable en un tiempo de ejecución acotado, cosa que los métodos clásicos no pueden ofrecer. Cuando un problema crece hasta tamaños dónde los métodos clásicos dejan de ser aplicables, ya sea por tiempo o memoria, un GA (o en su defecto cualquier meta-heurística bio-inspirada) son candidatos excelentes para obtener soluciones con una calidad aceptable, consumiendo una cantidad de recursos asumible. Los GAs son una de las familias más populares que forman parte del conjunto de algoritmos meta-heurísticos bio-inspirados. Dichos algoritmos han sido aplicados en centenares de dominios de forma satisfactoria, incluido el PDC.

    Aplicar un GA a un entorno dinámico de manera satisfactoria no es trivial y es necesario definir mecanismos extra. Los GAs son heurísticos poblacionales, dado que durante el proceso de ejecución no existe una única solución que se va mejorando, sino que existe un conjunto de ellas. Cuando trabajamos en un entorno dinámico y aparecen cambios, es posible que la población deje de ser capaz de encontrar soluciones satisfactorias al problema. Una solución trivial a este problema es descartar la población actual cuando aparezca un cambio y crear una nueva completamente de cero. Sin embargo, dicha estrategia descarta todo trabajo pasado, lo que la convierte en ineficiente y no aplicable al mundo real.

    Esta tesis se ha centrado, por lo tanto, en la aplicación de GAs para la detección de comunidades dinámicas en redes, en concreto, a estudiar aquellas técnicas que permiten reducir el tiempo de ejecución, en aras de hacer estos algoritmos aplicables al mundo real. Se identificaron principalmente dos escollos para aplicar un GA al PDC dinámico: i) la necesidad de adaptar los individuos a los cambios en la topología de la red para evitar la aparición de soluciones inválidas; ii) la necesidad de adaptar las poblaciones a cambios en la red para evitar que pierdan capacidades.

    Las principales contribuciones de la tesis doctoral pueden resumirse en:

    *) Respecto a la aparición de soluciones inválidas, se han propuesto tres operadores capaces de reparar un individuo, es decir, transformar una solución inválida en una solución válida de nuevo. A la hora de realizar el proceso de reparación, los mecanismos propuestos son capaces de aprovechar el conocimiento pasado, de tal manera que apenas se pierda información durante el proceso de reparación. Para probar la validez de dichos mecanismos se ha llevado un caso de uso en el que se integraron en un GA concreto para la detección de comunidades dinámicas y se probó el rendimiento de dicho GA usando una batería de pruebas compuesta por 66 redes sintéticas y dos reales.

    *) En cuanto al segundo problema abordado, en el estado del arte se pueden encontrar varias técnicas que permiten adaptar una población a un cambio del entorno de tal manera que no pierda capacidades y, entre ellas, las técnicas de inmigrantes son de las más populares. Aunque implementar dichas técnicas en un algoritmo genético es un proceso sencillo, su posterior ajuste no lo es tanto, ya que se tienen que configurar una serie de parámetros que pueden afectar de manera crítica al rendimiento del algoritmo. En aras de hacer este proceso más sencillo, esta tesis propone una nueva metodología que permite evaluar estrategias de inmigrantes en GAs en base a tres dimensiones diferentes: Calidad, Estabilidad y Velocidad. La metodología se diseñó con un propósito doble: por un lado, evaluar si una determinada estrategia de inmigrantes está mejorando o perjudicando alguna de las dimensiones mencionadas y, por otro, dar información sobre lo que podría estar ocurriendo en el caso de que alguna de las dimensiones se vea afectada negativamente. Finalmente, y para probar la validez de esta metodología se llevó a cabo un caso de uso en el que se evaluaron tres de las estrategias de inmigrantes más populares usando 18 redes dinámicas sintéticas.

    Se han realizado un conjunto de validaciones y análisis experimentales respecto a la utilización de GAs en el dominio de la deteccción de comunidades dinámicas que ha permitido establecer:

    *) Qué método, o métodos, son los más eficientes para adaptar los individuos de un GA diseñado para la detección de comunidades a los cambios del entorno y así evitar la aparición de soluciones inválidas.

    *) Cuál de las estrategias presentes en el estado del arte para adaptar la población de un GA a cambios en el entorno es la que mejor funciona para la versión dinámica del PDC y qué ventajas e inconvenientes presenta.

    *) Del conocimiento obtenido durante la realización de esta tesis, se ha tratado de establecer cómo podrían generalizarse los resultados obtenidos a otros dominios, es decir, cómo puede elegirse la mejor estrategia para adaptar las poblaciones de un GA en otros problemas dinámicos ajenos al del PDC.