ADDIC – Algoritmo distribuído para a descoberta de comunidades sobrepostas em grandes grafos

Página do item simplificado
dc.contributor.advisorPereira, Adriano César Machado
dc.contributor.advisorLatteshttp://lattes.cnpq.br/6813736989856243
dc.contributor.authorNascimento, João Paulo Barbosa
dc.contributor.authorLatteshttp://lattes.cnpq.br/8472333663591219
dc.contributor.refereePereira, Adriano César Machado
dc.contributor.refereeFreitas, Henrique Cota de
dc.contributor.refereeMartins, Carlos Augusto Paiva da Silva
dc.contributor.refereeAlmeida, Paulo Eduardo Maciel de
dc.contributor.refereePádua, Flávio Luis Cardeal
dc.date.accessioned2025-05-13T20:42:54Z
dc.date.available2025-05-13T20:42:54Z
dc.date.issued2019-09-26
dc.description.abstractRedes 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.
dc.description.abstractotherComplex networks are large dynamic systems that can be modeled by graphs. Many social, biological or technological systems are considered complex networks, including the Internet and the Web, real or virtual social networks and physical infrastructure networks such as transport and communication. The analysis of these networks, in the form of large graphs, provides important information about the characteristics of modeled systems. However, sequential processing of these graphs may require high computational cost or may not be feasible, depending on their size and complexity. To solve this problem we resort to parallel and distributed processing. This work proposes the parallel and distributed algorithm ADDIC, indicated for the process of detecting overlapping communities in a large complex network. The algorithm was designed from an important literature algorithm and also through a careful study of the Apache Spark parallel and distributed programming framework, combined with a detailed design of experiments. The experiments were performed on various types of graphs of different sizes, real and synthetic. The runtime, resource consumption (CPU and RAM), scalability and efficiency measures of the algorithm were evaluated. The results of the experiments indicate that ADDIC achieves its goal, which is to detect overlapping communities, and to present better runtime results than the main sequential algorithm in the literature. In addition, the proposed algorithm presents scalability close to linearity and good efficiency rates.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1447
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectAlgoritmos
dc.subjectRedes complexas
dc.subjectModelos matemáticos
dc.subjectRedes sociais
dc.subjectMídias sociais
dc.titleADDIC – Algoritmo distribuído para a descoberta de comunidades sobrepostas em grandes grafos
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
ADDIC – Algoritmo distribuído para a descoberta de comunidades.pdf
Tamanho:
2.67 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional