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

Origem: Wikilivros, livros abertos por um mundo aberto.
Conteúdo apagado Conteúdo adicionado
Criou nova página com '== Descrição da Aplicação == === Denominação === Algoritmo PageRank. === Contexto === A busca de informação não é uma tarefa trivial. A área da recuperaç...'
(Sem diferenças)

Revisão das 16h32min de 14 de fevereiro de 2013

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_ERR}

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.