Algoritmo Paralelo de Dinâmica de Partículas Aplicado ao Problema de Agrupamento em Grafos

• Hugo Resende
• Álvaro Luiz Fazenda
• Marcos Gonçalves Quiles

Resumo

Diversas aplicações podem ser naturalmente modeladas por meio de estruturas matemáticas combinatoriais como as redes complexas. Nessas estruturas, vértices bem relacionados podem indicar alguma informação potencialmente útil e, além disso, proporcionar uma melhor avaliação dos dados. Por essa razão, o problema de agrupamento em redes complexas, ou agrupamento em grafos, tem sido bastante estudado por pesquisadores de várias áreas. No entanto, a maioria dos algoritmos propostos têm encontrado dificuldades em agrupar vértices em grafos com milhares de vértices e arestas, sendo um dos grandes desafios, projetar algoritmos eficientes para tal fim. Um dos algoritmos propostos recentemente para o problema de agrupamento em grafos, que se utiliza da técnica de dinâmica de partículas como mecanismo de construção de soluções (agrupamentos) apresentou uma eficiência considerável em relação a demais algoritmos conhecidos, entretanto, possui complexidade quadrática, limitando a sua aplicação em grafos com muitas arestas e vértices. Objetivando superar limitações no desempenho computacional, bem como citado, pesquisadores recorrem, normalmente, a estratégias relacionadas ao processamento de alto desempenho, tal como a paralelização dos algoritmos em CPUs e em GPUs. Tendo isso em mente, o presente trabalho objetiva demonstrar que a paralelização do algoritmo de agrupamento em grafos baseado na técnica de dinâmica de partículas, implementada para CPUs, por meio do uso de diretivas OpenMP, pode ser uma alternativa válida na aplicação desse algoritmo em instâncias de grafos maiores.