ATRACTOR

Vimos que o vector \(x\) era vector fixo de \(P\), ou seja, \(x=Px\). Temos então \[\begin{array}{ccl} x_{i} & = & \sum_{j=1}^{n}p_{ij}x_{j}=\sum_{s_{j}=0}p_{ij}x_{j}+\sum_{s_{j}\neq0}p_{ij}x_{j}=\\ & = & \sum_{s_{j}=0}\frac{1}{n}x_{j}+\sum_{s_{j}\neq0}\left(\frac{1-p}{n}+p\frac{g_{ij}}{s_{j}}\right)x_{j}=\\ & = & \frac{1}{n}\sum_{s_{j}=0}x_{j}+\frac{1}{n}\sum_{s_{j}\neq0}x_{j}-\frac{p}{n}\sum_{s_{j}\neq0}x_{j}+p\sum_{s_{j}\neq0}\frac{g_{ij}}{s_{j}}x_{j}=\\ & = & \frac{1}{n}\left(\sum_{s_{j}=0}x_{j}+\sum_{s_{j}\neq0}x_{j}\right)-\frac{p}{n}\sum_{s_{j}\neq0}x_{j}+p\sum_{s_{j}\neq0}\frac{g_{ij}}{s_{j}}x_{j}=\\ & = & \frac{1}{n}-\frac{p}{n}\sum_{s_{j}\neq0}x_{j}+p\sum_{s_{j}\neq0}\frac{g_{ij}}{s_{j}}x_{j}=\\ & = & \frac{1-p\sum_{s_{j}\neq0}x_{j}}{n}+p\sum_{s_{j}\neq0}\frac{g_{ij}}{s_{j}}x_{j} \end{array}\] onde \(\sum_{s_{j}\neq0}x_{j}\) designa a soma dos valores de \(x_{j}\) para as páginas de índice \(j\) com pelo menos um link (ou seja, tais que \(s_{j}\neq0\)) e \(\sum_{s_{j}=0}x_{j}\) designa a soma dos valores de \(x_{j}\) para as páginas de índice \(j\) sem nenhum link (ou seja, tais que \(s_{j}=0\)). Note-se que \[\sum_{s_{j}=0}x_{j}+\sum_{s_{j}\neq0}x_{j}=\sum_{j=i}^{n}x_{j}=1\]

Suponhamos agora que todas as páginas possuem pelo menos um link, ou seja, \(s_{j}\neq0,\forall j\in\{1,2,...,n\}.\)

Então, temos que \(\sum_{s_{j}\neq0}x_{j}=\sum_{j=i}^{n}x_{j}=1\) e vem \[x_{i}=\frac{1-p}{n}+p\sum_{j=1}^{n}\frac{g_{ij}}{s_{j}}x_{j}\] ou seja, \[x_{i}=\frac{1-p}{n}+p\left(\frac{x_{j_{1}}}{s_{j_{1}}}+\frac{x_{j_{2}}}{s_{j_{2}}}+...+\frac{x_{j_{k}}}{s_{j_{k}}}\right)\] onde \(j_{1},j_{2},...,j_{k}\) são os índices das páginas que possuem um link para a página de índice \(i\).

Recordemos que a fórmula original de cálculo do PageRank é dada por \[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_{j}\) designa a página de índice \(j\), \(PR\left(P_{j}\right)\) o seu PageRank e \(C\left(P_{j}\right)\) o seu número de links.

É claro que \(C\left(P_{j}\right)=s_{j}\), mas qual a relação entre \(PR\left(P_{i}\right)\) e \(x_{i}\)? Observemos que, partindo da equação \[x_{i}=\frac{1-p}{n}+p\left(\frac{x_{j_{1}}}{s_{j_{1}}}+\frac{x_{j_{2}}}{s_{j_{2}}}+...+\frac{x_{j_{k}}}{s_{j_{k}}}\right)\] se multiplicarmos ambos os membros da equação por \(n\), temos \[nx_{i}=n\frac{1-p}{n}+np\left(\frac{x_{j_{1}}}{s_{j_{1}}}+\frac{x_{j_{2}}}{s_{j_{2}}}+...+\frac{x_{j_{k}}}{s_{j_{k}}}\right)\] \[nx_{i}=(1-p)+p\left(\frac{nx_{j_{1}}}{s_{j_{1}}}+\frac{nx_{j_{2}}}{s_{j_{2}}}+...+\frac{nx_{j_{k}}}{s_{j_{k}}}\right)\]

De facto, temos que \(PR\left(P_{i}\right)=nx_{i}\) e o valor do PageRank coincide, a menos do factor \(n\), com a probabilidade de, a longo prazo, o utilizador se encontrar na página de índice \(i\). Assim, o PageRank de uma página qualquer varia entre \(0\) e \(n\) (mais propriamente, entre \(1-p\) e \(n\)) e soma do PageRank de todas as páginas é \[\sum_{i=1}^{n}PR\left(P_{i}\right)=\sum_{i=1}^{n}nx_{i}=n\sum_{i=1}^{n}x_{i}=n.1=n\]

E se nem todas as páginas possuírem pelo menos um link? Neste caso, temos \(PR\left(P_{i}\right)<nx_{i},\forall j\in\{1,2,...,n\}\) e a soma dos valores do PageRank é menor do que \(n\). Por que será?

Próxima Página