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

Página complementar do artigo submetido ao WPerformance 2018

Gustavo S. Carnivali1, Alex B. Vieira2, Paulo A. A. Esquef1, Artur Ziviani1

1. Laboratório Nacional de Computação Científica (LNCC/MCTIC)

2. Departamento de Ciência da Computação -- Universidade Federal de Juiz de Fora (UFJF)

Contato: JLIB_HTML_CLOAKING

Resumo

Este artigo reporta resultados de uma investigação sobre o problema de detecção de comunidades em redes complexas representadas. 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.

Links para as bases de dados

Email
Polblogs
Reactome
PGP
DBLP
Amazon
Youtube
LiveJournal

 

Código do MRAV+ML (em C++)

O código do MRAV+ML é distribuído aqui nos termos da Licença Pública Geral GNU, com o propósito de disseminação técnico-científica. Os autores não se responsabilizam pela utilização do código fora da seara acadêmica.

Resultados Complementares (em construção)