<p>El uso de los grafos para modelar sistemas complejos es creciente en multitud de ámbitos.Son extremadamente útiles para representar interacciones, relaciones sociales e intercambio de información en Internet. Analizando la estructura de estas redes, comprendiendo como interaccionan sus distintos elementos, se puede entender mejor el comportamiento del sistema en su conjunto. A menudo, los nodos que conforman estos grafos tienden a formar grupos altamente conectados entre sí y con otros grupos. Esta propiedad es conocida como estructura de comunidades solapadas y este trabajo se ha centrado en el problema de la detección de comunidades solapadas en redes dinámicas y su caracterización. Para entender la problemática desde su base, en este trabajo se estudia la teoría de grafos desde sus deniciones básicas hasta las características generales, luego se hace un breve análisis de las redes sociales desde tres perspectivas: a nivel de elementos, de grupos y de redes. A continuación, se detallan los tipos de problemas en la búsqueda de comunidades, tales como comunidades con información global, local, solapadas y dinámicas, se mencionan y describen algunos de los algoritmos más relevantes para la detección de comunidades disjuntas y solapadas. Posteriormente, se trata el tema central del presente trabajo, las redes dinámicas, enfocándose en el análisis e implementación del algoritmo dinámico AFOCS (Adaptive Finding Overlapping Community Structure) [34], un algoritmo adaptativo para la detección,actualización y rastreo de la evolución de comunidades solapadas en redes dinámicas no dirigidas y sin pesos, apuntando a la actualización de forma rápida y eciente como consecuencia de la inserción y/o eliminación de nodos y/o aristas dentro de una red compleja. De forma complementaria, se formula una extensión para analizar grafos ponderados no dirigidos, con el propósito de tomar en cuenta la importancia del peso en las relaciones entre nodos, y poder establecer un criterio adicional para formar una comunidad. Luego para comprobar el impacto de la incorporación de pesos en AFOCS, se compara el rendimiento del método frente a otros algoritmos dinámicos</p>
<p>The use of graphs to model complex systems belonging to dierent domains such as social networks and biology is increasing. They are extremely useful to represent interactions, social relations and information exchange between nodes. Analizing the structure of these complex systems as graphs helps to understand the behaviour of the systems as a whole. This works focuses on the problem of detecting overlapping communities in dynamics graphs.An extension to the dynamic algorithm AFOCS is proposed to analize dynamics weighted and undirected graphs. A detailed experimental evaluation shows that the proposed approach achieves competitive results w.r.t state of the art approaches</p>
last modification
Licenciado en Ciencias de la Ingeniería
Ingeniero Civil en Informáticatítulo
INGENIERIA CIVIL INFORMATICA
<p>El uso de los grafos para modelar sistemas complejos es creciente en multitud de ámbitos.Son extremadamente útiles para representar interacciones, relaciones sociales e intercambio de información en Internet. Analizando la estructura de estas redes, comprendiendo como interaccionan sus distintos elementos, se puede entender mejor el comportamiento del sistema en su conjunto. A menudo, los nodos que conforman estos grafos tienden a formar grupos altamente conectados entre sí y con otros grupos. Esta propiedad es conocida como estructura de comunidades solapadas y este trabajo se ha centrado en el problema de la detección de comunidades solapadas en redes dinámicas y su caracterización. Para entender la problemática desde su base, en este trabajo se estudia la teoría de grafos desde sus deniciones básicas hasta las características generales, luego se hace un breve análisis de las redes sociales desde tres perspectivas: a nivel de elementos, de grupos y de redes. A continuación, se detallan los tipos de problemas en la búsqueda de comunidades, tales como comunidades con información global, local, solapadas y dinámicas, se mencionan y describen algunos de los algoritmos más relevantes para la detección de comunidades disjuntas y solapadas. Posteriormente, se trata el tema central del presente trabajo, las redes dinámicas, enfocándose en el análisis e implementación del algoritmo dinámico AFOCS (Adaptive Finding Overlapping Community Structure) [34], un algoritmo adaptativo para la detección,actualización y rastreo de la evolución de comunidades solapadas en redes dinámicas no dirigidas y sin pesos, apuntando a la actualización de forma rápida y eciente como consecuencia de la inserción y/o eliminación de nodos y/o aristas dentro de una red compleja. De forma complementaria, se formula una extensión para analizar grafos ponderados no dirigidos, con el propósito de tomar en cuenta la importancia del peso en las relaciones entre nodos, y poder establecer un criterio adicional para formar una comunidad. Luego para comprobar el impacto de la incorporación de pesos en AFOCS, se compara el rendimiento del método frente a otros algoritmos dinámicos</p>
<p>The use of graphs to model complex systems belonging to dierent domains such as social networks and biology is increasing. They are extremely useful to represent interactions, social relations and information exchange between nodes. Analizing the structure of these complex systems as graphs helps to understand the behaviour of the systems as a whole. This works focuses on the problem of detecting overlapping communities in dynamics graphs.An extension to the dynamic algorithm AFOCS is proposed to analize dynamics weighted and undirected graphs. A detailed experimental evaluation shows that the proposed approach achieves competitive results w.r.t state of the art approaches</p>