Como ordenar páginas da Internet 
O modelo
O PageRank baseia-se no seguinte modelo - suponhamos que um dado utilizador, dispondo de uma lista completa de todas as páginas da Internet, vai percorrendo-as por dois métodos possíveis:
- escolhendo aleatoriamente qualquer uma das páginas da Internet
- seguindo um dos links da página onde se encontra no momento
Note-se que a primeira hipótese evita que o utilizador pare ao deparar-se com uma página sem nenhum link ou que fique limitado a um conjunto de páginas sem links para páginas exteriores. Assim, o utilizador pode continuar a "surfar" na Internet indefinidamente, podendo a qualquer momento visitar qualquer página.
Para construir um modelo matemático, vamos supor o seguinte:
- A probabilidade de o utilizador seguir um dos links da página onde se encontra em vez de escolher aleatoriamente uma das páginas da Internet é constante e designa-se por \(p\), com \(0<p<1\). Habitualmente, escolhe-se \(p=0,85\). Claro que, para que o modelo tenha algum significado, convém que as escolhas do utilizador não sejam aleatórias a maior parte das vezes, por isso convém escolher um valor próximo de \(1\), mas não demasiado próximo, uma vez que tal tornaria os cálculos mais demorados (ver "convergência").
- Se o utilizador optar por escolher aleatoriamente uma das páginas da Internet, todas elas têm a mesma probabilidade de serem escolhidas. Assim, supondo que existem \(n\) páginas na Internet, a probabilidade de uma qualquer ser escolhida é \(\frac{1}{n}\).
- Se o utilizador optar por seguir um dos links da página onde se encontra, todos eles têm a mesma probabilidade de serem escolhidos. Assim, supondo que a página de índice \(j\) tem \(s_{j}\) links, a probabilidade de escolher qualquer um deles é \(\frac{1}{s_{j}}\).
Sendo assim, supondo que o utilizador se encontra na página de índice \(j\), qual é a probabilidade de escolher de seguida a página de índice \(i\)? Se a página de índice \(j\) não tem nenhum link, então a próxima página terá de ser escolhida aleatoriamente entre todas as páginas da Internet, pelo que, designando essa probabilidade por \(p_{ij}\), temos \[p_{ij}=\frac{1}{n}\]
No entanto, se a página de índice \(j\) tem algum link, então a próxima página tanto poderá ser escolhida aleatoriamente entre todas as páginas da Internet como poderá ser algum dos seus links. Sendo assim, temos:
- se a página de índice \(i\) não é nenhum dos links da página de índice \(j\), a única maneira de a atingir é através de uma escolha aleatória, pelo que \[p_{ij}=\left(1-p\right)\frac{1}{n}\]
- se a página de índice \(i\) é um dos links da página de índice \(j\), ela pode ser escolhida por qualquer um dos dois métodos, pelo que \[p_{ij}=\left(1-p\right)\frac{1}{n}+p\frac{1}{s_{j}}\]
Mais geralmente, temos
\[p_{ij}=\left(1-p\right)\frac{1}{n}+p\frac{g_{ij}}{s_{j}}\] onde \(g_{ij}\) é \(1\) se existe um link da página de índice \(j\) para a página de índice \(i\) e \(0\) caso contrário. Claro que, ao fixar o índice \(j\) e variar o índice \(i\) entre \(1\) e \(n\), o somatório de todos os valores \(g_{ij}\) dá-nos o número de links da página de índice \(j\), ou seja, \({\displaystyle \sum_{i=1}^{n}g_{ij}=s_{j}}\).
Uma cadeia de Markov é um sistema formado por um número finito de estados possíveis sujeito a um processo de evolução de tal forma que, em cada momento, apenas um dos estados é possível e tal que a probabilidade de transição entre dois estados depende apenas desses estados. Neste caso, se considerarmos que os estados possíveis são as páginas da Internet e que o processo de mudança consiste na navegação na Internet segundo o modelo anterior, concluímos que estamos na presença de uma cadeia de Markov, uma vez que a probabilidade de mudança da página de índice \(j\) para a página de índice \(i\) é o valor \(p_{ij}\)que foi definido acima e que apenas depende das páginas de índice \(i\) e \(j\).
Note-se que, mesmo sabendo qual foi a página inicial, em geral não é possível saber, a dado instante, qual a página em que o utilizador se encontra. Sabemos, no entanto, que existe uma certa probabilidade de, após ter visitado \(m\) páginas, se encontrar na página de índice \(i\), a qual designaremos por \(x_{i}^{\left(m\right)}\). Além disso, sabendo o valor destas probabilidades para um certo \(m\), podemos calcular de imediato qual a probabilidade de a página seguinte ser a de índice \(i\). Por definição, vem \[x_{i}^{\left(m+1\right)}=p_{i1}x_{1}^{\left(m\right)}+p_{i2}x_{2}^{\left(m\right)}+...+p_{in}x_{n}^{\left(m\right)}=\sum_{j=1}^{n}p_{ij}x_{j}^{\left(m\right)},\forall m\epsilon\mathbb{N}_{0}\] uma vez que cada parcela \(p_{ij}x_{j}^{\left(m\right)}\) representa a probabilidade de, após ter visitado \(m\) páginas, se encontrar na página de índice \(j\) e, de seguida, mudar para a página de índice \(i\). Seja:
- \(x^{\left(m\right)}=\left(x_{1}^{\left(m\right)},x_{2}^{\left(m\right)},...,x_{n}^{\left(m\right)}\right)\)
- \(P=\left(p_{ij}\right)_{1\leq i,j\leq n}\)
Então, temos \[x^{\left(m+1\right)}=Px^{\left(m\right)},\forall m\epsilon\mathbb{N}_{0}\] pelo que \[x^{\left(m\right)}=P^{m}x^{\left(0\right)},\forall m\epsilon\mathbb{N}_{0}\] onde \(x^{\left(0\right)}=\left(x_{1}^{\left(0\right)},x_{2}^{\left(0\right)},...,x_{n}^{\left(0\right)}\right)\) é o vector cuja componente \(x_{i}^{\left(0\right)}\) representa a probabilidade de partir da página de índice \(i\), pelo que se trata de um vector de probabilidades (ou seja, um vector com componentes não negativas e com soma igual a \(1\)).
Dado que as entradas da matriz \(P\) são todas positivas, \(P\) é uma matriz regular e, como consequência do teorema de Frobenius, a sucessão de vectores de probabilidades \(x^{\left(m\right)}\) converge para um vector de probabilidades \(x=\left(x_{1},x_{2},...,x_{n}\right)\), independentemente do vector \(x^{\left(0\right)}\). Além disso, como \(P\) é aplicação contínua, da equação acima deduzimos que \(x\) é vector fixo de \(P\); de facto é o único vector de probabilidade que verifica a equação \(Pz=z\).
Deste modo, mesmo não conhecendo o vector inicial \(x^{\left(0\right)}\) (e, portanto, não sabendo qual poderá ter sido a página inicial), sabemos que a probabilidade de o utilizador se encontrar na página de índice \(i\) se aproxima do valor \(x_{i}\), uma vez que \(x_{i}^{\left(m\right)}\rightarrow x_{i}\) para todo \(i\epsilon\left\{ 1,2,...,n\right\} \). Podemos, então, encarar o valor \(x_{i}\) como a probabilidade de, a longo prazo, o utilizador se encontrar na página de índice \(i\).
Será que existe alguma relação entre \(x_{i}\) e o PageRank da página de índice \(i\)?
