Desarrollo de un algoritmo genético para análisis de problemas basados en grafos
Author
Muñiz Velázquez, DiegoEntity
UAM. Departamento de Ingeniería InformáticaDate
2018-06Subjects
Redes sociales; Algoritmo genético; Grafo; Informática
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
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.
Files in this item
Google Scholar:Muñiz Velázquez, Diego
This item appears in the following Collection(s)
Related items
Showing items related by title, author, creator and subject.
-
Desarrollo de un algoritmo de enjambre para análisis de problemas basados en grafos
Moralejo Lorenzo, Diego
2018-05 -
Estudio de algoritmos de computación basada en grafos aplicado al análisis de redes
Sanz Sacristán, Pinar
2018-01