Definição: mede a importância de cada pág. na web com base na probabilidade de um usuário encontrar essa página. Páginas mais linkadas têm maior probabilidade de serem encontradas

• Evita fraudes ao considerar a importância das páginas que apontam para ela, de forma recursiva.
• Usa como base cadeia de Markov construída a partir do grafo de docs da internet

Premissas:

• O usuário inicia na web a partir de uma página aleatória. A navegação ocorre seguindo os links das páginas. Probabilidade igual de seguir links em uma página.
• A probabilidade de acesso é calculada após X transições aleatórias respeitando o grafo de ligações. Problema: se começar em certa página, outras podem ter PageRank zero.
• Introdução do fator de amortecimento (damping factor) d. (1-d) é a probabilidade de saltar para qualquer documento do grafo após visualizar a página atual.
• Existem dois modos de calcular o PR(j):

1. Método da amostragem: segue X transições aleatórias, considerando prob. d de seguir um link do documento atual e prob. (1-d) de saltar para qualquer documento. PR(j) = aj/X
2. Algoritmo iterativo: definir valor inicial PR(j) = 1/N para cada documento j, atualizando iterativamente o PageRank de cada página, baseada no valor da iteração anterior

$$ P R(j):=\frac{1-d}{N}+d \sum_{i\ \in \ L(j)} \frac{P R(i)}{N u m L i n k s(i)} $$

Onde, N = nº total de docs, NumLinks(i) = nº de links na página i; L(j) = conj. de docs com links para doc j.