Análise de grafos baseada em processamento paralelo assíncrono centrado em vértices: aplicações em dados de escala planetária

Resumo

O processamento de grafos de alta escala -- chamados grafos em escala planetária, ou escala Web -- tem atraído o interesse em diversas aplicações como comércio eletrônico, redes de computadores, redes sociais, biologia (interação proteica), entre muitos outros. Para se processar tais grafos, os quais possuem milhões de vértices e bilhões de arestas, tem se utilizado recursos de processamento distribuído organizados em clusters computacionais gerenciados por arcabouços como o Hadoop. O problema de tal abordagem é o fato de que as exigências para se construir e gerenciar tais clusters muitas vezes trazem complexidades maiores do que as necessárias para se processar e analisar os grafos de interesse. Ocorre assim um desvio de recursos, pois o meio requer mais esforço do que o fim. Dessa maneira, torna-se desejável a capacidade de se processar grafos em escala planetária em um único nó computacional. Para este propósito, neste trabalho, se irá trabalhar com técnicas centradas em vértice combinadas com processamento paralelo assíncrono. As técnicas centradas em vértice permitem que propriedades locais dos grafos sejam calculadas sem que o grafo tenha que passar por uma varredura; já as técnicas de processamento paralelo assíncrono permitem que um grafo ocupando Terabytes de um único disco de armazenamento seja processado gradualmente em passos que cabem em memória. Com estas técnicas pretende-se o desenvolvimento de novos algoritmos capazes de calcular propriedades ainda não exploradas de grandes grafos processados em um único nó computacional. Tais propriedades serão usadas na definição de um arcabouço de análise capaz de revelar padrões, compreensão, e tomada de decisão.