Uma análise sobre a acurácia e a escalabilidade de algoritmos paralelos de detecção de comunidades em grafos

Abstract

Detecção de comunidades é um tipo de análise topológica amplamente utilizada em análise de grafos de diversas áreas como análise de redes sociais, bioinformática e sistemas de recomendação. O problema compreende detectar componentes que apresentam alta densidade interna e baixa densidade externa. Devido ao rápido crescimento do volume de dados de diversas aplicações e à ampla utilização deste tipo de análise, diversas pesquisas em abordagens paralelas e distribuídas para resolver o problema de detecção de comunidades surgiram. Alguns algoritmos possuem maior popularidade, resultando em uma extensa quantidade de pesquisa dentro de otimizações para processamento paralelo. Outros algoritmos, mesmo possuindo bons resultados de acurácia em testes, não apresentam o mesmo nível de profundidade de pesquisa em suas versões paralelas e distribuídas. Esta pesquisa aborda a acurácia e escalabilidade de três algoritmos de detecção de comunidades. A partir dos experimentos realizados são propostas diretrizes para a utilização de cada algoritmo de acordo com as necessidades do usuário. Além disso, é explorado o comportamento das abordagens paralelas e possíveis melhorias são propostas.

Community detection is a type of topological analysis widely used in graph analysis in several fields such as social network analysis, bioinformatics and recommendation systems. The problem involves detecting components that have high internal density and low external density. Due to the rapid growth in the volume of data from a variety of applications and the wide use of this type of analysis, several researches in parallel and distributed approaches to solve the problem of community detection have emerged. Some algorithms are more popular, resulting in an extensive amount of research on optimizations for parallel processing. Other algorithms, which posses better accuracy results in tests, do not present the same level of research depth in their parallel and distributed versions. This research addresses the accuracy and scalability of three community detection algorithms. User guidelines are proposed based on the experiments results. In addition, the behavior of the parallel approaches is explored and possible improvements are proposed.