ATRACTOR

We may compute the values for the \(x_{i}\) without the prior knowledge of the PageRank values. In fact, given the properties of the vector \(x\), it is enough to identify the unique eigenvector associated to eigenvalue \(1\) of the matrix \(P\) with coordinates larger than or equal to zero and such that their sum is equal to \(1\). However, due to the size of the matrix \(P\), it is convenient to use an iterative approach instead of a direct calculation. We start by noting that the definition of vector \(x\) suggests an iterative method for this calculation. As \(x\) appear as the limit of the sequence of probability vectors \(x^{\left(m\right)}\), which is iteratively defined by \(x^{\left(m+1\right)}=Px^{\left(m\right)}\), all that we need is to identify a starting probability vector \(x^{\left(0\right)}\) and, at each iteration step, multiply the matrix \(P\) by the column matrix corresponding to the current approximation.

Assuming that \(s_{j}\neq0,\forall j\epsilon\left\{ 1,2,\cdots,n\right\} \), we find that \[\begin{array}{ccl} x_{i}^{\left(m+1\right)} & = & \sum_{j=1}^{n}p_{ij}x_{j}^{\left(m\right)}=\\ & = & \sum_{j=1}^{n}\left(\frac{1-p}{n}+p\frac{g_{ij}}{s_{j}}\right)x_{j}^{\left(m\right)}=\\ & = & \frac{1-p}{n}\sum_{j=1}^{n}x_{j}^{\left(m\right)}+p\sum_{j=1}^{n}\frac{g_{ij}}{s_{j}}x_{j}^{\left(m\right)}. \end{array}\]

Moreover, as \(x^{\left(m\right)}\) is a probability vector, it follows that for every \(m\), we have that \[\sum_{j=1}^{n}x_{j}^{\left(m\right)}=\sum_{j=1}^{n}x_{j}^{\left(0\right)}=1,\forall m\epsilon\mathbb{N}.\]

Hence,we may write that \[\begin{array}{ccl} x^{\left(m+1\right)} & = & \frac{1-p}{n}\sum_{j=1}^{n}x_{j}^{\left(m\right)}+p\sum_{j=1}^{n}\frac{g_{ij}}{s_{j}}x_{j}^{\left(m\right)}=\\ & = & \frac{1-p}{n}+p\sum_{j=1}^{n}\frac{g_{ij}}{s_{j}}x_{j}^{\left(m\right)}=\\ & = & \frac{1-p}{n}+p\left(\frac{x_{j_{1}}^{\left(m\right)}}{s_{j_{1}}}+\frac{x_{j_{2}}^{\left(m\right)}}{s_{j_{2}}}+\cdots+\frac{x_{j_{k}}^{\left(m\right)}}{s_{j_{k}}}\right), \end{array}\] where \(j_{1},j_{2},\cdots,j_{k}\) are the indices of web pages that include a link pointing towards page \(i\). Assuming that no web page includes links pointing to itself, this method coincides with the Jacobi method to compute the values for \[PR^{*}\left(P_{i}\right)=\frac{PR\left(P_{i}\right)}{n}=x_{i}.\] However, this statement is no longer true if \(s_{j}=0\) for some \(j\epsilon\left\{ 1,2,\cdots,n\right\} \), that is, if there exist web pages that do not include at least one link.

Beginning