Comparing community detection algorithms in graphs
Title
Comparing community detection algorithms in graphsAuthor(s)
Directors
Hernández-Pereira, ElenaDate
2022Center/Dept./Entity
Enxeñaría informática, Grao enDescription
Traballo fin de grao. Enxeñaría Informática. Curso 2021/2022Abstract
[Abstract] The detection of communities in graphs has been a very discussed topic in recent years
due to the raise of social networks. This topic is not a simple one, and as such, many different
solutions have been proposed over the years to try and find communities in these networks.
In this project we compare the results of different community detection algorithms when
applied to a real live graph. This comparison is made using a set of quality metrics that will
give us information of the algorithm’s performance. With this information at hand we have
seen that these algorithms perform very differently from each other and that the graph to
which they are applied is a very important part in the results they return. [Resumo] A detección de comunidades en grafos foi un tema moi discutido nos últimos anos debido
ao auxe das redes sociais. Este tema de estudo non é sinxelo, e por iso propuxéronse moitas
solucións diferentes ao longo dos anos para tratar de atopar comunidades nestas redes. Neste
proxecto comparamos os resultados de diferentes algoritmos de detección de cando se aplican
a un grafo real. Esta comparación realízase empregando un conxunto de métricas de calidade
que nos darán información do rendemento dos algoritmos. Coa informacion obtida, vimos
que estes algoritmos teñen un comportamento moi distinto entre si e que o grafo ao que se
aplican é unha parte moi importante nos resultados que devolven.
Keywords
Graph
Community detection
Louvain
Modularity
Label propagation
Connected components
Community detection
Louvain
Modularity
Label propagation
Connected components