Desarrollo de un algoritmo genético para análisis de problemas basados en grafos

Abstract

El uso de grafos para modelar diferentes problemas es un enfoque que nos puede ayudar a resolver un gran número de ellos. Aun con la ayuda de los grafos, muchos de estos problemas presentan una complejidad computacional elevada, lo que hace necesaria la implementación de algoritmos heurísticos para facilitar el tratamiento de la información que estos nos aportan. Este Trabajo de Fin de Grado tratará el problema de la detección de comunidades en las Redes Sociales (RRSS). El imparable crecimiento de las RRSS y el inmenso número de usuarios conectados que en ellas se encuentran, las han convertido en un lugar donde conseguir una gran cantidad de información. Una de las características básicas de las RRSS, es la de permitir a sus usuarios agrupar, organizar y clasificar sus conexiones en diferentes grupos o “círculos”. Los usuarios que formen un grupo tendrán una característica en común, pudiendo ser compañeros de trabajo, amigos o “hobbies” por ejemplo. Esta clasificación variará en función del usuario y la RS a la que estemos haciendo referencia. Al observar estas relaciones entre usuarios en las RRSS, rápidamente podemos observar que es posible tratarlas como un grafo donde, cada usuario se corresponde con un nodo y las relaciones entre usuarios con las aristas. En este TFG se pretende desarrollar un algoritmo heurístico bio-inspirado que determinará automáticamente los diferentes grupos de usuarios en un dataset específico (Facebook en nuestro caso). Para evaluar la calidad de las soluciones encontradas se utilizará la densidad entre los nodos dentro y fuera de su comunidad, o grupo, para decidir si esta está bien definida o se podría mejorar.