1º Exemplo

Consideremos três páginas \(A\), \(B\) e \(C\) tais que existe apenas uma ligação da página \(A\) para a página \(B\) e uma ligação da página \(B\) para a página \(C\). Aplicando a fórmula do PageRank com \(p=0,85\), temos

\(\begin{array}{ccl} PR\left(A\right) & = & 0,15\\ PR\left(B\right) & = & 0,15+0,85\times PR\left(A\right)=0,15+0,85\times0,15=0,2775\\ PR\left(C\right) & = & 0,15+0,85\times PR\left(B\right)=0,15+0,85\times0,2775=0,385875. \end{array}\)

Neste caso, obtivemos facilmente os valores exactos do PageRank de cada página.

Notemos que \(PR\left(A\right)<PR\left(B\right)<PR\left(C\right)\).

2º Exemplo

Consideremos três páginas \(A\), \(B\) e \(C\) tais que existe apenas uma ligação da página \(A\) para a página \(B\), uma ligação da página \(B\) para a página \(C\) e uma ligação da página \(C\) para a página \(A\). Aplicando a fórmula do PageRank com \(p =0,85\), temos

\[PR\left(A\right)=0,15+0,85\times PR\left(C\right)\] \[PR\left(B\right)=0,15+0,85\times PR\left(A\right)\] \[PR\left(C\right)=0,15+0,85\times PR\left(B\right)\]

Neste caso, não é possível obter de imediato os valores exactos do PageRank de cada página. Teremos de resolver o sistema formado pelas equações dadas acima cujas incógnitas são \(PR\left(A\right), PR\left(B\right)\) e \(PR\left(C\right)\), que tem como solução \[PR\left(A\right)=PR\left(B\right)=PR\left(C\right)=1\]

Como seria de esperar, todas as páginas têm o mesmo PageRank. Para ver outros exemplos, pode experimentar esta app, na qual é possível seleccionar até um máximo de \(6\) páginas (\(A\), \(B\), \(C\), \(D\), \(E\) e \(F\)) e interligá-las do modo que desejar.

De um modo geral, para calcularmos os valores do PageRank de um conjunto de \(n\) páginas ligadas entre si teremos que resolver um sistema de \(n\) equações (as equações do PageRank de cada uma das páginas) com \(n\) incógnitas (o valor do PageRank de cada uma das páginas). Se o valor de \(n\) for pequeno, não há problema. No entanto, a base de dados do Google é formada por vários milhões de páginas, o que torna pouco prático o cálculo do valor exacto do PageRank. Neste caso, o que se faz é um cálculo iterativo de valores aproximados do PageRank, sendo estes valores tanto mais próximos dos valores exactos quanto maior for o número de iterações.

Assim, considerando as três páginas \(A\), \(B\) e \(C\) do segundo exemplo dado, vamos atribuir um PageRank inicial igual a \(1\) a cada uma delas. Aplicando a fórmula do PageRank, temos

\[PR\left(A\right)=0,15+0,85\times PR\left(C\right)=0,15+0,85\times1=1\] \[PR\left(B\right)=0,15+0,85\times PR\left(A\right)=0,15+0,85\times1=1\] \[PR\left(C\right)=0,15+0,85\times PR\left(B\right)=0,15+0,85\times1=1.\]

Ou seja, obtivemos o mesmo valor (\(1\)) de PageRank. Tal aconteceu porque, como vimos, este é o valor exacto do PageRank de cada página.

E se tivéssemos atribuído outro PageRank inicial a cada página? Por exemplo, tomando um valor inicial de \(0,5\) e aplicando a fórmula do PageRank, vem

\[PR\left(A\right)=0,15+0,85\times PR\left(C\right)=0,15+0,85\times0,5=0,575\] \[PR\left(B\right)=0,15+0,85\times PR\left(A\right)=0,15+0,85\times0,5=0,575\] \[PR\left(C\right)=0,15+0,85\times PR\left(B\right)=0,15+0,85\times0,5=0,575.\]

Aplicando novamente a mesma fórmula, mas utilizando os valores obtidos acima, vem

\[PR\left(A\right)=0,15+0,85\times PR\left(C\right)=0,15+0,85\times0,575=0,63875\] \[PR\left(B\right)=0,15+0,85\times PR\left(A\right)=0,15+0,85\times0,575=0,63875\] \[PR\left(C\right)=0,15+0,85\times PR\left(B\right)=0,15+0,85\times0,575=0,63875,\]

e assim sucessivamente. Após \(10\) iterações, temos

\[PR\left(A\right)=PR\left(B\right)=PR\left(C\right)=0,90156...,\]

e, após \(67\) iterações, temos

\[PR\left(A\right)=PR\left(B\right)=PR\left(C\right)=0,99999....\]

Ou seja, os valores de PageRank calculados aproximam-se cada vez mais do valor exacto. De facto, tal acontece sempre, independentemente do valor de PageRank atribuído inicialmente a cada página (neste exemplo, com um valor inicial de \(1000\) para cada página, em apenas \(100\) iterações obteríamos um valor de aproximadamente \(1,00044\) para cada página), e isto é verdade não só neste exemplo, como também para qualquer conjunto de páginas ligadas entre si. Por que será?


Nota: o processo iterativo descrito pode ser visto como a aplicação de um método iterativo de resolução de sistemas, denominado por método de Jacobi. Existe também um outro método iterativo, denominado por método de Gauss-Seidel, que difere do anterior na medida em que os novos valores calculados em cada iteração são de imediato usados nos cálculos. No segundo exemplo dado anteriormente, depois de atribuir um valor inicial de \(0,5\) a cada uma das páginas, teríamos ainda na primeira iteração

\(\begin{array}{ccl} PR\left(A\right) & = & 0,15+0,85\times PR\left(C\right)=0,15+0,85\times0,5=0,575\\ PR\left(B\right) & = & 0,15+0,85\times PR\left(A\right)=0,15+0,85\times0,575=0,63875\\ & & (\mbox{usamos }PR\left(A\right)=0,575\mbox{ em vez de }PR\left(A\right)=0,5)\\ PR\left(C\right) & = & 0,15+0,85\times PR\left(B\right)=0,15+0,85\times0,63875=0,69293..\\ & & (\mbox{usamos } PR\left(B\right)=0,63875 \mbox{ em vez de }PR\left(B\right)=0,5). \end{array}\)

Em geral, o método de Gauss-Seidel converge mais rapidamente do que o método de Jacobi.