Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank: diferenças entre revisões
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.