Como ordenar páginas da Internet Reformatar


Como calcular

Como se calcula o PageRank?

Suponhamos que temos um conjunto indexado \(P_{1},P_{2},P_{3},...,P_{n}\) de \(n\) páginas ligadas entre si e sem ligações com outras páginas. Dada uma página \(P_{j}\), seja \(PR\left(P_{j}\right)\) o valor do seu PageRank e \(C\left(P_{j}\right)\) o número de links que partem dessa página.

A fórmula original de cálculo do PageRank, desenvolvida pelos próprios fundadores do Google (Larry Page e Sergey Brin), é a seguinte: \[PR\left(P_{i}\right)=\left(1-p\right)+p\left(\frac{PR\left(P_{j1}\right)}{C\left(P_{j1}\right)}+\frac{PR\left(P_{j2}\right)}{C\left(P_{j2}\right)}+...+\frac{PR\left(P_{jk}\right)}{C\left(P_{jk}\right)}\right)\] onde

  • \(p\) é um parâmetro compreendido entre \(0\) e \(1\) (habitualmente \(p=0,85\))
  • \(PR\left(P_{i}\right)\) designa o valor do PageRank da página \(P_{i}\)
  • \(j_{1},j_{2},...,j_{k}\) são os índices das páginas que possuem um link para a página \(P_{i}\)
  • \(PR\left(P_{j1}\right),PR\left(P_{j2}\right),...,PR\left(P_{jk}\right)\) designa o valor do PageRank dessas páginas
  • \(C\left(P_{j1}\right),C\left(P_{j2}\right),...,C\left(P_{jk}\right)\) designa o número de links dessas páginas

Ou seja, ao valor mínimo do PageRank atribuído a cada página, dado por \(1-p\), juntamos parcelas que resultam do modo como a página \(P_{i}\) está relacionada na rede da Internet. Deste modo, o PageRank de cada página é transmitido equitativamente por todos os seus links, sendo este valor ponderado pelo parâmetro \(p\).

Note-se que um link de uma página \(A\) para uma página \(B\) pode ser interpretado como um "voto" da página \(A\) para a página \(B\).

Assim, para que uma página tenha um valor elevado de PageRank, não interessa apenas que receba um grande número de ligações de outras páginas, mas também que essas páginas tenham um PageRank elevado e que esse PageRank transmitido seja partilhado com o menor número possível de outras páginas (atendendo ao facto de o PageRank transmitido por uma página ser partilhado por todos os links dessa página, receber um link de uma página que possui apenas \(5\) links no total pode ser mais vantajoso do que receber um link de uma página com um PageRank superior mas com, digamos, \(100\) links).

Segundo esta fórmula, o PageRank de uma página qualquer está definido em função do PageRank das páginas que possuem um link para essa página. Como podemos então calcular efectivamente o seu valor, se à partida não conhecemos o PageRank de nenhuma página?

Nota: se, na fórmula original de cálculo do PageRank, \[PR\left(P_{i}\right)=\left(1-p\right)+p\left(\frac{PR\left(P_{j1}\right)}{C\left(P_{j1}\right)}+\frac{PR\left(P_{j2}\right)}{C\left(P_{j2}\right)}+...+\frac{PR\left(P_{jk}\right)}{C\left(P_{jk}\right)}\right)\] dividirmos ambos os membros por \(n\), temos \[\frac{PR\left(P_{i}\right)}{n}=\left(\frac{1-p}{n}\right)+p\left(\frac{PR\left(P_{j1}\right)}{nC\left(P_{j1}\right)}+\frac{PR\left(P_{j2}\right)}{nC\left(P_{j2}\right)}+...+\frac{PR\left(P_{jk}\right)}{nC\left(P_{jk}\right)}\right)\] ou seja, \[PR^{*}\left(P_{i}\right)=\left(\frac{1-p}{n}\right)+p\left(\frac{PR^{*}\left(P_{j1}\right)}{C\left(P_{j1}\right)}+\frac{PR^{*}\left(P_{j2}\right)}{C\left(P_{j2}\right)}+...+\frac{PR^{*}\left(P_{jk}\right)}{C\left(P_{jk}\right)}\right)\] onde \[PR^{*}\left(P_{j}\right)=\frac{PR\left(P_{j}\right)}{n}\] para qualquer página \(P_{j}.\)

Por vezes, é conveniente tomar \(PR^{*}\) como sendo o valor do PageRank de uma página em vez de \(PR\). De facto, como \(0<PR\left(P_{j}\right)\leq n\) para qualquer página \(P_{j}\), vem que \(0<PR^{*}\left(P_{j}\right)\leq1\) para qualquer página \(P_{j}\). Segundo esta definição de PageRank, o seu valor está sempre compreendido entre \(0\) e \(1\), independentemente do número de páginas a considerar.