View
127
Download
7
Category
Preview:
DESCRIPTION
Algoritmo PageRank utilizado pela Google para atribuir uma importância numérica a cada nó de um grafo.
Citation preview
03/09/14
Inteligência ArtificialPageRank
03/09/14
Introdução
● Continuaremos com grafos, mas o objetivo agora não é busca
● Agora queremos descobrir qual o nó “mais importante” em um grafo, ou ordenar todos os nós por algum critério de importância
03/09/14
Introdução
● Este tipo de algoritmo foi desenvolvido há décadas por outras áreas como biblioteconomia (para calcular a importância de autores em grafos de citações)
● Em 1998, foi publicado um artigo com aplicação específica para ranquear páginas da web, o PageRank
03/09/14
Introdução
● Apesar de ter sido concebido especialmente para páginas web, ele passou a ser aplicado em diversas áreas, pois serve para qualquer grafo
● Ex.: sumarizadores automáticos de texto, análise de redes sociais, análise de propagação de tumores, informática forense, ecologia
03/09/14
Introdução
● Nesta aula, veremos uma versão simplificada do PageRank, mais próxima do conceito geral de Cadeias de Markov e sem a necessidade de álgebra linear avançada
03/09/14
PageRank
03/09/14
PageRank
03/09/14
PageRank
● O algoritmo PageRank consiste em atribuir um valor para um nó de um grafo de acordo com quantas arestas chegam até ele (as chamaremos de votos), ponderadas pelo valor dos nós de origem● Ex.: Um site X linkado por 1000 sites “fracos” pode ter um
valor menor que o de um site Y linkado por um site Z “forte”
● Em outras palavras, ser linkado pelo Terra pode valer mais que ser linkado por 1000 blogs pessoais desconhecidos
03/09/14
PageRank
● Mas se o valor de uma página depende do valor das páginas que linkam para ela, como calcular o valor dessas outras páginas?
● Poderia ser um loop infinito ou até uma recursão, mas felizmente pode ser simplificado
03/09/14
PageRank
● Vamos iniciar todos os nós com o mesmo valor (1) e calcular o valor final dos nós em vários passos
● Cada nó manda um voto para cada um de seus vizinhos com um peso igual a PR/n, onde n é o número de vizinhos e PR é seu valor atual
● Cada vizinho recebe seus votos e os redistribui no passo seguinte
● Repita por um número grande de vezes k (ex.: 100)
03/09/14
PageRank
Inicialize vetor PR com n 1's, onde n é o número de nós do grafo
Repita k vezes //(ex.: k = 100)Para cada nó i do grafo
PR[i] ← 0
Para cada nó j do grafo com link para i
PR[i] ← PR[i] + PR[j] / numVizinhos(j) //Onde numVizinhos(j) é o número de links saindo do nó j
Fim Para
PR[i] ← PR[i] * d + (1 – d) //d é um parâmetro entre 0 e 1, ex.: 0.85
Fim Para
Fim Repita
03/09/14
PageRank
● Ex.: Considere o grafo ao lado
● Vamos usar um vetor de valores com um elemento para cada nó:
PR = [1, 1, 1, 1]
03/09/14
PageRank
● Todos começam com valor 1
● Agora vamos distribuir os votos igualmente entre os vizinhos de cada nó e considerando d = 0.85
03/09/14
PageRank
● PR[A] ← 0.15 + 0.85 * (1/1)● PR[B] ← 0.15 + 0.85 * (½)● PR[C] ← 0.15 + 0.85 * (½
+ 1/1 + 1/1)● PR[D] ← 0.15 + 0.85 * (0)● Atualizando...● PR = [1, 0.575, 2.275
0.15]
03/09/14
PageRank
● Repetimos com os novos valores● PR[A] ← 0.15 + 0.85 * (2.275/1)● PR[B] ← 0.15 + 0.85 * (½)● PR[C] ← 0.15 + 0.85 * (½ +
0.575/1 + 0.15/1)● PR[D] ← 0.15 + 0.85 * (0)● Atualizando...● PR = [2.08375, 0.575, 1.19125,
0.15]
0.575--------
2.275--------
0.15--------
03/09/14
PageRank
● Repetimos k vezesaté que os valoresestabilizem e obtemos o resultado final:
● PR = [1.49, 0.783, 1.577, 0.15]
03/09/14
PageRank
● Logo, a página C é a mais importante, seguida pela A e depois pela B, sendo a D a menos importante
03/09/14
PageRank
● Em um grafo pequeno como este podemos até deduzir o ranking apenas olhando
● Mas apenas contando links não teríamos como diferenciar A de B, o que conseguimos com o PR
● Em grafos maiores (ex.: a web inteira), o PR é essencial
Recommended