Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank

Descrição da Aplicação

Denominação

Algoritmo PageRank.

Contexto

A busca de informação não é uma tarefa trivial. A área da recuperação de informação vem lidando com esse problema há décadas, antes mesmo da criação da Web, desenvolvendo sistemas para busca de jornais, artigos científicos e patentes. A busca na Web se torna mais difícil ainda, devido a sua natureza evolutiva de constante crescimento e modificação.

Uma solução proposta para o problema de busca de páginas na Web que é utilizado pelo Google é o algoritmo PageRank. Ele tenta medir a importância de cada página levando em consideração a topologia da rede formada pelas ligações entre as páginas através dos hyperlinks. Mesmo sendo proposto inicialmente para páginas da Web, ele pode ser aplicado em qualquer rede, onde o resultado final do algoritmo é um valor numérico atribuído a cada nodo, medindo sua respectiva influência naquela rede.

Algoritmo

Numa rede com n nodos, atribui-se inicialmente o valor de 1/n para cada um. Depois disso, realizamos uma regra de atualização um determinado número k de vezes. A regra de atualização é a seguinte: cada nodo compartilha seu valor atual de PageRank igualmente com todos os nodos que segue, e cada nodo atualiza seu valor para ser a soma das partes que recebeu. A teoria do PageRank diz que até mesmo uma pessoa que clica em links aleatoriamente vai, eventualmente, parar de clicar. A probabilidade, a qualquer passo, que uma pessoa continue clicando é dado por um fator de amortecimento (damping factor) d, que geralmente é configurado para ter o valor 0,85. O fator de amortecimento é subtraído de 1 e o resultado é adicionado ao produto do fator de amortecimento pela soma das partes que o nodo recebeu.

Para cada vértice $v$:
    $PR(v,0)={\frac {1}{N}}$
    $VA={v\in V}$
Para cada iteração $t$, enquanto $|VA|>0$:
    Para cada vértice $v\in VA$:
        $PR(v,t+1)={\frac {1-d}{N}}+d\sum _{u\in M(v)}{\frac {PR(u,t)}{L(u)}}$
    $VA={v\in V:|PR(V,t+1)-PR(V,t)|>MAX_{E}RR}$

Exemplo de Funcionamento

Na Figura XX é possível visualizar os nodos de um grafo com seus respectivos valores de PageRank. Podemos observar que o nodo B é o que tem o maior valor, e pode ser considerado o mais relevante, de acordo com o conceito do algoritmo. Observe também que o nodo J, mesmo tendo muitas arestas de entrada, não tem um PageRank alto, o que indica que os nodos que estão ligados a ele não tem tanta relevância.

Requisitos

• Escalabilidade: A escalabilidade é necessária devido ao fato da rede ser dinâmica, ou seja, novos vértices e ligações podem ser criados ou removidos a qualquer instante, e do grande volume de dados que chega na faixa dos milhões de vértices e bilhões de arestas.
• Armazenamento: A aplicação não demanda muito armazenamento em memória principal devido para o cálculo em si, devido às propriedades comutativa e associativa do cálculo do valor PageRank, não sendo necessário armazenar num mesmo instante todos os valores utilizados. Entretanto, devido a magnitude dos grafos trabalhados na aplicação, é necessário uma quantidade significativa de espaço em disco para armazenar o grafo. Já o resultado (saída) do algoritmo demanda pouco espaço, pois é necessário apenas os IDs dos vértices e seus respectivos valores de PageRank finais.
• Latência: O dinamismos da rede torna o cálculo do PageRank necessário constantemente. A taxa de atualização depende do cenário de aplicação, podendo ser semanal, diário ou até mesmo horário. Nesse caso, o cálculo do valor de PageRank de todos os vértices deve ser feito em tempo hábil.
• Tolerância a falhas: O algoritmo necessita que os valores de PageRank dos vértices estejam sincronizados em relação às iterações, ou seja, somente valores de uma mesma iteração devem ser utilizados para atualização. Como para o cálculo de um vértice é necessário os valores de todos os vizinhos, é necessário que haja uma estabilidade dos nodos de computação.

Paralelizações existentes

As primeiras propostas de paralelização do algoritmo PageRank foram desenvolvidas implementando a versão matricial do algoritmo em resolvedores de sistema linear paralelos.

Outra estratégia utilizada é o esquema "URL Host", que aproveita a estrutura hierárquica da WEB para fazer a parelização. Basicamente o que ele faz é agrupar os vértices de página de um mesmo domínio (host) e fazer a computação distribuída. Apesar de eficiente, essa estratégia fica limitada a grafos que representem páginas de internet, sendo inadequada para uma abordagem mais genérica.

Existem algumas versões de PageRank que fornecem valores aproximados, que na maioria das vezes é justificado pela eficiência no tempo de execução, e uma vertente desses algoritmos faz uma abordagem paralela. Uma dessas abordagens utiliza um esquema MapReduce que utiliza um modelo probabilístico e utiliza o método de Monte Carlo para calcular os valores.

Há ainda tentativas de implementação do algoritmo em placas gráficas (GPUs), que são arquiteturas fortemente paralelas e com enorme poder de processamento. Apesar de eficientes, a maioria dessas abordagens fica limitada pela memória local limitada, então para aplicações práticas de alto porte, é necessária uma estratégia auxiliar.

Projeto

Oportunidades de paralelização

Como o cálculo do rank de um nodo em uma iteração depende do rank na iteração anterior dos nodos que apontam para este nodo, este passo de calcular o novo rank pode ser executado paralelamente para cada nodo.

O valor do rank anterior não pode ser mudado enquanto esse passo é executado e isso pode ser evitado. Ao terminar esse passo, é necessário sincronizar as linhas de execução para que a próxima iteração leia valores de ranks atualizados.

A paralelização pode ser ampliada se os somatórios de ranks forem divididos. A lista de nodos apontadores seria dividida e o rank parcial seria calculado separadamente, já que soma em ordem diferente tem o mesmo resultado. Entretanto isso cria uma etapa adicional para combinar os resultados parciais.

Entretanto essa oportunidade paralelização não garante balanceamento de carga entre cada thread, porque enquanto um nodo pode ser apontado por apenas um nodo, outro pode ser apontado por inúmeros. O balanceamento pode ser melhorado fazendo as threads somarem números aproximados de nodos; os nodos que tem mais apontadores seriam divididos entre mais threads, enquanto uma thread pode fazer o somatório para mais de um nodo.

Padrões de acesso aos dados

Cada nodo tem como dados o cojunto de nodos para o qual ele aponta e o valor de page rank atual. É necessário que o nodo em cada iteração veja um grafo invertido, que tenha a lista de nodos que apontam para ele. E ele precisará saber o valor do rank atual desses nodos junto com o número de nodos para os quais eles apontam ou apenas a divisão entre esses dois valores.

Quando um algoritmo paralelo executa no mesmo computador, as threads podem ter memória compartilhada e isso permite que cada thread leia todas as informações que precisar sobre o grafo e o custo disso é relativamente baixo.

Quando o volume de dados é muito grande, o processamento teria tempo de execução longo e os dados podem não caber em um só disco rígido. A solução seria fazer processamento é distribuído. Isso requer que cada computador do cluster receba os dados necessários dos nodos que ele precisará e ao final de cada iteração o nodo precisará saber o novo valor de rank de cada nodo que ele precisa e isso gera muitas mensagens de comunicação na rede.

Padrões de comunicação

É necessário fazer comunicação para sincronizar as threads no final de cada iteração para que o novo valor de rank seja atualizado no momento certo para não prejudicar as outras threads que ainda estejam executando e também para começar a próxima iteração lendo valores de rank atualizados. Essa sincronização pode ser vista como duas barreiras, em que a primeira espera todos os somatórios terminar e a segunda espera todos os ranks serem atualizados.

Em processamento distribuído, o novo valor de rank deve ser enviado para todas as threads que usarão esse valor na próxima iteração. Assim, o número de mensagens trocadas na rede em cada iteração seria igual ao número de arestas do grafo, e esse grande número de mensagens pode sobrecarregar a rede.

Linha do tempo integrada

Quando há uma thread por nodo, cada thread processa de maneira independente sua lista de apontadores e no final é necessário esperar todas as outras threads terminar para poder atualizar o rank do nodo e receber novos valores de rank. Além da comunicação para sincronização, em implementação distribuída, é necessário comunicação para enviar e receber valores do rank calculados durante a iteração.

Desenvolvimento

Hadoop

A implementação do PageRank usando Hadoop executa um número de iterações definido como argumento do programa. Cada iteração tem uma fase de “map” e “reduce”, além das fases de leitura de dados da iteração anterior e escrita para o próxima iteração. O programa começa lendo um arquivo de entrada contendo o grafo e carrega os dados do grafo no Hadoop.

O “damping factor” é um argumento opcional do programa. O valor padrão é 0.85 e para desativar basta definir o valor como 1.0.

Estratégias de paralelização

A etapa “map” é executada paralelamente para cada dado. Ela tem como entrada a chave sendo o identificador do nodo e como valor o rank atual do nó. Cada nodo passa no “map” uma vez e tem como saída cada nodo apontado por ele e o valor de rank dividido pelo número de nodos apontados.

A etapa “reduce” tem como entrada a chave sendo o identificador do nodo e uma lista de valores de rank/número de nodos apontados já calculados na etapa anterior. Essa etapa vai somar os valores dessa lista e retornar o novo valor de rank para o nodo identificado pela chave.

Como foi falado, essa estratégia não garante balanceamento de carga na etapa “reduce”, porque o tempo de execução para nodos com mais apontadores seria mais longo por ter mais valores no iterador para somar.

Estratégias de armazenamento

Ao terminar uma iteração os dados são salvos no sistema de arquivos virtual distribuído do Hadoop (HDFS) para serem lidos no início da próxima iteração.

Estratégias de comunicação

A gerência da execução é feita pela função principal do programa que inicia cada iteração de map-reduce. Assim, o Hadoop é encarregado de criar as threads e dividir a carga, sincronizar e transportar dados nas etapas map e reduce, e escrever a saída da iteração.