Método Rápido de Agrupamento de Vértices para Detecção de Comunidades em Redes Complexas de Larga-escala

• Gustavo S. Carnivali
• Alex B. Vieira
• Paulo A. A. Esquef
• Artur Ziviani

DOI: https://doi.org/10.5753/wperformance.2018.3332

Resumo

Este artigo reporta resultados de uma investigação sobre o problema de detecção de comunidades em redes complexas. Na literatura dedicada a esse assunto, um algoritmo iterativo, denominado Método de Louvain (ML), se destaca como opção eficaz e rápida para o problema. Entretanto, as primeiras iterações do ML são sua parte mais custosa. Neste artigo, propõe-se um Método Rápido de Agrupamento de Vértices (MRAV) em grafos como uma opção mais rápida do que as primeiras iterações do ML. Através de experimentos envolvendo redes grandes do mundo real, demonstra-se que o sistema proposto MRAV+ML identifica comunidades com modularidade similar ao ML (redução média menor de 3%), mas com redução média de aproximadamente 42% no tempo de execução.