Um Algoritmo Paralelo Eﬁciente para Cálculo de Centralidade em Grafos - Cruz, Leonardo Carlos da; Murta, Cristina Duarte (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), 2013)
Estudos em áreas tão diversas quanto sistemas de comunicação, Internet e Web, computação móvel, sistemas biológicos, redes sociais e redes de transporte, dentre outras, apresentam em comum o fato de que todos esses sistemas podem ser modelados por grafos. A quantidade de elementos participantes nessas redes complexas tem alcançado escalas cada vez maiores, o que requer o uso de processamento paralelo para a análise dos grafos. Neste artigo apresentamos um novo algoritmo paralelo para o cálculo exato de centralidades em grafos grandes, usando o paradigma de programação MapReduce/Hadoop. O objetivo é computar as distâncias entre os vértices e extrair medidas de centralidades decorrentes dessas distâncias, fazendo uso eﬁciente dos recursos computacionais. Para avaliar o algoritmo proposto foram processados diversos grafos e os resultados comparados com algoritmos sequenciais e paralelos. Os experimentos mostraram que o algoritmo proposto faz uso eﬁciente da memória e do espaço em disco, comparado à outras implementações.