Análise de dados sobre grafos em larga escala por meio de processamento paralelo assíncrono centrado em vértices

Since the birth of web 2.0, users no longer just consume but are now active creators of content that is going to be consumed by other users. This new dynamic took data generation to a whole new scale, called planetary-scale or web-scale. Often, this data represents relationships between its elements, such as in social networks, recommendation systems, online boards, email networks, scientific citation networks, and others. Analyzing how information flows and how nodes influence each other in several of such networks is a widely regarded problem; While Belief Propagation, which is the fundamental algorithm for these types of inference, is widely used, it historically lacked convergence guarantees for real-world networks. However, even though recently alternative methods such as LinBP solve the convergence problems of the original algorithm, its scalability when dealing with large-scale problems remains a challenge. Also, several of the works proposed to solve this issue, do so by relying on specific infrastructures such as supercomputers and computational clusters. Motivated by these challenges we propose a new algorithm, called VCBP, that aims to provide a scalable framework for belief propagation on largescale problems, such as when graphs do not fit the main memory. We do so by combining stateof- the-art asynchronous vertex-centric parallel processing with state-of-the-art belief propagation algorithm. Our algorithm maintains the same accuracy rate while achieving performance orders of magnitude higher than former LinBPs implementation. Due to the asynchronous nature of our algorithm, VCBP demands fewer iterations before convergence than any previous algorithm. Additionally, we analyze our algorithm in the task of node classification, achieving significant results over real-world datasets. Our findings indicate that there is unexplored potential in todays widely available modern hardware, specifically concerning parallelism, sparking a shift towards a more cost-efficient and ubiquitous data mining scenario.Desde o surgimento da web 2.0, os usuários não mais apenas consomem conteúdo, mas também são responsáveis agora por criar conteúdo que será consumido por outros usuários. Essa nova dinâmica levou a produção de dados à uma nova e surpreendente escala, chamada de escala planetária. Muitas vezes tais dados representam relacionamentos entre seus elementos, como é o caso em redes sociais, sistemas de recomendação, fórums online, redes de email, redes de citação científica, entre outras. Analisar o fluxo de informações e como os nós influenciam uns aos outros nesses domínios é um problema recorrente; Apesar do algoritmo Belief Propagation ser um dos principais algoritmos utilizados nesse contexto, o algoritmo historicamente apresentou problemas de garantias de convergência quando aplicado à redes reais. Contudo, apesar de recentemente métodos alternativos como LinBP focarem em resolver o problema de convergência do algoritmo original, a escalabilidade do algoritmo em grafos de larga escala continua sendo um desafio. Além disso, muitas das propostas que tentam resolver o problema de escalabilidade necessitam de infraestrutura adicional como supercomputadores e clusters computacionais. Com a motivação desses desafios, essa tése propoe um novo algoritmo, chamado VCBP, que tem como objetivo prover um arcabouço escalável para Belief Propagation em problemas de larga escala, como ocorre nos casos em que o grafo não cabe na memória principal. A proposta combina técnicas de processamento paralelo assíncrono centrado em vértices com avanços de estado-da-arte no algoritmo de Belief Propagation. O VCBP é capaz de alcançar novos patamares de performance que são ordens de magnitude melhores que a implementação do LinBP. Além disso, devido à natureza assíncrona do algoritmo são necessárias menos iterações até que a convergência seja alcançada quando comparado com outras soluções. Por fim, analisamos também o algoritmo quando aplicado à tarefa de classificação, alcançando resultados significativos em bases de dados reais. Nossas descobertas indicam que existe um grande potencial inexplorado na tecnologia de hardware largamente disponível atualmente, especialmente em relação ao paralelismo, apontando para a oportunidade de uma computação mais acessível e com melhor custo-benefício