Comparing community detection algorithms in graphs

Abstract

[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.