Como é calculado o PageRank do Google?

A artigo a seguir contém algumas explicações matemáticas, mas ao final dele ficará claro o conceito de PageRank.

O Google, e todos os outros sites de busca baseados em contexto, utilizam um ranqueamento de páginas. É isso, entre outras coisas, que faz uma página aparecer antes de outra nos resultados de uma busca. Como pode valer um bom dinheiro a posição na buscas, existe uma legião de SEOs (Search Engine Optimizers) à solta dizendo como fazer para melhorar o PageRank (PR daqui pra frente) de uma página. Mas afinal, como é calculado o PageRank do Google?

Exatamente como é calculado o PR do Google eu não sei e duvido que mais do que umas 5 ou 6 pessoas saibam, e todas trabalham no Google com sigilo de informação em seus contratos. Mas posso explicar o funcionamento básico do sistema, baseado, entre outros documentos, em um paper publicado pelos própios Sergey Brin e Lawrence Page. Sim, os caras que montaram o Google já disseram uma vez como fizeram. Esse artigo foi publicado na época em que ainda estavam na universidade de Stanford e mostra o design do sistema que àquela altura indexava 24 milhões de páginas. Vamos lá…

O método de cálculo do PR
O método é iterativo. Grosso modo, para um cálculo iterativo, assumimos alguns valores iniciais, fazemos todos os cálculos e voltamos à primeira equação aplicando os valores que acabamos de calcular. Repete-se o processo até que exista a convergência, isto é, os valores comecem a se “repetir”.

A equação do PageRank:
PR(A) = (1-d) + d( PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

onde:
d: fator de damping (amortecimento)
PR(Tn): PageRank da página Tn
C(Tn): links contidos na página Tn

Eis porque o método é iterativo, para calcular o PR de página A, eu preciso saber o PR de todas as outras páginas que apontam pra ela. É uma questão do tipo “ovo ou a galinha”. A solução é assumir um valor arbitrário para algumas variáveis (no caso alguns PRs), calcular tudo e recomeçar, só que dessa vez ao invés de “chutar” um valor inicial, utiliza-se os resultados que acabamos de obter.

O C(Tn) é o número de links que a página contém. Imagine que uma página aponte para outras 14 além da sua, a importância desse link no cálculo é 1/15 do PR dela. Confuso? Na verdade é simples. Se uma página com PR 0,8 aponta para a sua e outras 14 páginas (portanto 15 no total), o peso dela na termo de somas da equação é 0,8/15 = 0,05333.

O d, fator de damping, possui uma importância matemática muito grande, ele é fortemente responsável pela convergência do sistema. A cada iteração o valor de cada PR deve se aproximar do seu valor final, em um sistema convergente isso acontece. Se na iteração 15 o PR de uma determinada página era 0.067564, e na 16 0.067563, na 17 0.067563 novamente, é bem prová­vel que o valor “real” tenha sido encontrado. Esse valor de “d” é inicialmente “chutado”, e se não garantir a convergência do sistema, recomeçamos com um novo “chute”. No paper, Brin e Page recomendam 0.85 como valor inicial. Tem embutido nisso o que se chama de “matemágica”. Uma variação mà­nima em d pode fazer com que toda a matriz tenha um mal comportamento. Acreditem, é de fazer chorar…

Exemplo
Imagine uma “web” com apenas duas páginas (tá, eu sei que não parece grande coisa, mas funciona). A página A aponta para B, que aponta de volta para A, como na figura abaixo.

######figura de backlinks#####

Vamos admitir os valores iniciais dos PRs como 0 e o d igual a 0.85, e começarmos as iterações.

iteração 0:
PR(A) = (1 - 0.85) + 0.85*0 = 0.15
PR(B) = (1 - 0.85) + 0.85*0.15 = 0.2775

repare que já utilizei o valor calculado para PR(A) no cálculo de PR(B).

iteração 1:
PR(A) = 0.15 + 0.85 * 0.2775 = 0.385875
PR(B) = 0.15 + 0.85 * 0.385875 = 0.47799375

iteração 2:
PR(A) = 0.15 + 0.85 * 0.47799375 = 0.5562946875
PR(B) = 0.15 + 0.85 * 0.5562946875 = 0.622850484375

e assim por diante.

OBS: isso soará pedante, mas por favor, poupem-me de emails com considerações sobre autovalores, algarismos significativos, garantias de convergência, etc… Eu conheço muito bem o assunto e esse é um artigo para leigos.

Parece simples mas é um cálculo gigantesco. Imagine que na média cada página contenha links para outras 10, com isso serão necessárias 22 operações matemáticas para cada linha [PR(A), PR(B), etc...]. Em um sistema que indexe 1 bilhão de páginas, serão 22 bilhões de operações matemáticas por rodada! Considerando-se que o número de iterações pode passar das centenas de milhares os valores passam a ser astronômicos.

Na realidade é ainda pior, o número de links é apenas um dos critérios utilizados, colocando-se todos os outros pode-se chegar facilmente à casa dos trilhões de operações.

Google toolbar
O que esses números minúsculos têm a ver com o PR apresentado na barra de ferramentas do Google? É apenas uma suposição (apesar de fazer sentido do ponto de vista matemático), provavelmente eles estabelecem o maior PR como sendo 10 e normalizam, com uma escala logarí­timica, o resto.

Tenho certeza que voltarei a esse artigo no futuro, tentando torna-lo mais claro. Seria ótimo que deixassem comentários com observações, dúvidas, etc… para que eu possa melhora-lo.

Também posso dizer por experiência própria que o método funciona, é o que tenho utilizado na vecom para aprimorar a nova leva de resultados que deverá entrar no ar em breve.