Algoritmo Para C Lculo De Centralidade Em Grafos

WSCAD-SSC 2013 - XIV Simpósio em Sistemas Computacionais
___________________________________________________________________________________________________

Um Algoritmo Paralelo Eficiente para Cálculo de Centralidade em Grafos
Leonardo Carlos da Cruz
Departamento de Computação
CEFET-MG
Belo Horizonte, Brasil
Email: [e-mail]

Cristina Duarte Murta
Departamento de Computação
CEFET-MG
Belo Horizonte, Brasil
Email: [e-mail]

de grafos grandes.
Nesse contexto, apresentamos o AHEAD (Advanced
Hadoop Exact Algorithm for Distances), um algoritmo paralelo para processamento de grafos grandes, implementado em MapReduce/Hadoop. Nosso objetivo é investigar a aplicabilidade do modelo MapReduce ao processamento de grafos, particularmente ao processamento das distâncias entre os vértices, bem como a escalabilidade desse processamento em grafos com quantidades de vértices e arestas em várias escalas, e também o uso eficiente dos recursos computacionais no procedimento.
A computação de medidas de centralidade em grafos apresenta barreiras no que diz respeito à complexidade de sua computação [2]. Essas medidas, que incluem o diâmetro e o raio do grafo, tornam-se difíceis, senão proibitivas, de serem calculadas em grafos de escala muito grande [3]. Assim, a questão a ser avaliada é que tamanhos de grafos podemos analisar, por meio de algoritmos paralelos, para obter suas medidas exatas de centralidade. Para grafos maiores, podemos ter apenas um cálculo aproximado destas medidas [3], [4].
Esse trabalho dá continuidade ao trabalho desenvolvido em [5], em que foi proposto o algoritmo HEDA (Hadoop based Exact Diameter Algorithm), que encontra medidas exatas de centralidade para grafos de tamanhos moderados. No entanto, o algoritmo HEDA apresenta limitações quanto ao uso do espaço de armazenamento de dados [6].
Essas limitações têm relação com o uso que o algoritmo faz da memória principal e o modelo de armazenamento de dados do Hadoop no sistema de arquivos.