ATRACTOR

Como vimos, a entropia é dada por \[E=-\sum_{i,j=1}^{n}x_{j}p_{ij}log_{2}\left(p_{ij}\right)\] ou seja, \[E=-\sum_{j=1}^{n}x_{j}\left(\sum_{i=1}^{n}p_{ij}log_{2}\left(p_{ij}\right)\right)=\sum_{j=1}^{n}q_{j}x_{j}\] onde \[q_{j}=-\sum_{i=1}^{n}p_{ij}log_{2}\left(p_{ij}\right)\]

Para cada \(j\epsilon\left\{ 1,\ldots,n\right\} \), o valor de \(q_{j}\) vai depender do número de links que a página de índice \(j\) possui. Se a página de índice \(j\) possui \(s_{j}\) links, com \(s_{j}\neq0\), então temos \(s_{j}\) valores de \(p_{ij}\) iguais a \(\frac{1-p}{n}+\frac{p}{s_{j}}\) e \(\left(n-s_{j}\right)\) valores iguais a \(\frac{1-p}{n}\), pelo que \[\begin{array}{ccl} q_{j} & = & -s_{j}\left(\frac{1-p}{n}+\frac{p}{s_{j}}\right)log_{2}\left(\frac{1-p}{n}+\frac{p}{s_{j}}\right)-\left(n-s_{j}\right)\frac{1-p}{n}log_{2}\frac{1-p}{n}=\\ & = & -p\left(\frac{s_{j}\left(1-p\right)}{np}+1\right)log_{2}\left(1+\frac{np}{s_{j}\left(1-p\right)}\right)-log_{2}\frac{1-p}{n}=\\ & = & pf\left(\frac{1-p}{np}s_{j}\right)-log_{2}\frac{1-p}{n} \end{array}\] onde \(f(x)=-\left(x+1\right)log_{2}\left(1+\frac{1}{x}\right)\), com \(x>0\). Uma vez que a função \(f\) é estritamente crescente, podemos concluir que, quanto maior for o número de links, \(s_{j}\), maior será o valor de \(q_{j}\). Temos então que o valor máximo de \(q_{j}\) é dado por \[Q=-n.\frac{1}{n}log_{2}\frac{1}{n}=log_{2}n\] e é obtido apenas quando a página possui links para todas as páginas \(\left(s_{j}=n\right)\) ou quando não tem nenhum link \(\left(s_{j}=0\right)\). De facto, em ambos os casos temos \(p_{ij}=\frac{1}{n}\) para todo \(i\epsilon\left\{ 1,\ldots,n\right\} \).

Relativamente ao valor mínimo, este é obtido quando a página tem apenas um link \(\left(s_{j}=1\right)\). Neste caso, os valores de \(p_{ij}\) são todos iguais a \(\frac{1-p}{n}\), excepto um, que é igual a \(\frac{1-p}{n}+p\). Logo, o valor mínimo é dado por \[\begin{array}{ccl} q_{j} & = & -\left(\frac{1-p}{n}+p\right)log_{2}\left(\frac{1-p}{n}+p\right)-\left(n-1\right).\frac{1-p}{n}log_{2}\frac{1-p}{n}=\\ & = & -p\left(\frac{1-p}{np}+1\right)log_{2}\left(1+\frac{np}{1-p}\right)-log_{2}\frac{1-p}{n} \end{array}\]

Note-se que os valores \(Q\) e \(q\) não dependem da página em questão, isto é, \(q\leq q_{j}\leq Q\) para todo \(j\epsilon\left\{ 1,\ldots,n\right\} \). Logo, vem \[\sum_{j=1}^{n}qx_{j}\leq\sum_{j=1}^{n}q_{j}x_{j}\leq\sum_{j=1}^{n}Qx_{j}\]

Além disso, temos que \[\sum_{j=1}^{n}qx_{j}=q\sum_{j=1}^{n}x_{j}=q.1=q\] e \[\sum_{j=1}^{n}Qx_{j}=Q\sum_{j=1}^{n}x_{j}=Q.1=Q.\]

Portanto, vem \[q\leq E\leq Q\]

Conclui-se assim que \(q\) é o valor mínimo possível de entropia do sistema, atingido apenas quando cada página possui um e um só link, enquanto que \(Q\) é o valor máximo possível de entropia do sistema, atingido apenas quando cada página possui todos ou nenhum link. De facto, a primeira situação corresponde à situação de menor incerteza possível, na qual, independentemente da página onde o utilizador se encontra, há sempre uma e uma só página com mais probabilidade de ser escolhida do que as outras, enquanto que a segunda situação corresponde à situação de maior incerteza possível, na qual a escolha da próxima página é totalmente aleatória, uma vez que têm todas a mesma probabilidade de serem escolhidas.

Notas:

- Nem sempre é verdade que a entropia aumenta de cada vez que se aumenta o número de links de uma página, pois tal pode fazer com que diminuam os valores de PageRank das páginas com mais links.

- Dado um valor de \(p\) fixo, tanto o valor máximo \(Q\) como o valor mínimo \(q\) aumentam com o número de páginas \(n\).

- Dado um valor de \(n\) fixo, quanto maior for o valor do parâmetro \(p\), menor será o valor de \(q\) e vice-versa. Quando o valor de \(p\) tende para \(0\), o valor de \(q\) tende para o valor máximo \(Q\). Quando o valor de \(p\) tende para \(1\), o valor de \(q\) tende para \(0\).

- O valor de \(Q\) não depende do parâmetro \(p\).

- Independentemente da situação, quando o valor de \(p\) tende para \(0\), os valores de \(q_{j}\) tendem para \(Q\), pelo que a entropia do sistema tende para o valor máximo. Por outro lado, quando o valor de \(p\) tende para \(1\), os valores de \(q_{j}\) tendem para \(log_{2}\left(s_{j}\right)\). Assim, se todas as páginas tiverem apenas um link, a entropia tenderá para \(0\).

- Mesmo que algumas páginas tenham mais do que um link, se o seu PageRank tender para \(0\) quando o valor de \(p\) tende para \(1\), então a entropia do sistema também tenderá para \(0\).