ADDIC – Algoritmo distribuído para a descoberta de comunidades sobrepostas em grandes grafos
Carregando...
Data
2019-09-26
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Redes complexas são sistemas grandes e dinâmicos que podem ser modelados por grafos. Muitos sistemas sociais, biológicos ou tecnológicos são considerados redes complexas, dentre eles a Internet e a Web, as redes sociais reais ou virtuais e as redes de infraestrutura física, tais como redes de transporte e de comunicação. A análise destas redes, na forma de grandes grafos, provê informações importantes acerca das características dos sistemas modelados. No entanto, o processamento sequencial destes grafos pode requerer alto custo computacional ou mesmo ser inviável, dependendo de seu tamanho e complexidade. Para solucionar esse problema recorre-se ao processamento paralelo e distribuído. Este trabalho propõe o algoritmo paralelo e distribuído ADDIC, indicado para o processo de detecção de comunidades sobrepostas em uma rede complexa de grande porte. O algoritmo foi projetado a partir de um importante algoritmo da literatura denominado DEMON e também por meio de um estudo criterioso do framework de programação paralela e distribuída Apache Spark, aliado a um planejamento detalhado de experimentos. Os experimentos foram executados em vários tipos de grafos de diferentes tamanhos, reais e sintéticos. O tempo de execução, consumo de recursos (CPU e Memória RAM) e medidas de escalabilidade e eficiência do algoritmo foi avaliado. Os resultados dos experimentos indicam que o ADDIC alcança seu objetivo, que é detectar comunidades sobrepostas, além de apresentar resultados de tempo de execução melhores que o principal algoritmo sequencial da literatura. Além disso, o algoritmo proposto apresenta escalabilidade próxima à linearidade e boas taxas de eficiência.
Descrição
Palavras-chave
Algoritmos, Redes complexas, Modelos matemáticos, Redes sociais, Mídias sociais