0
$\begingroup$

I am trying to understand the pageRank algorithm by reading the original article:

http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

I have some issues understanding the algorithm at paragraph 2.6 . I try to report it here. This reads:

$R_0 \leftarrow S$

loop:

$R_{i+1} \leftarrow AR_i$

$d \leftarrow ||R_{i}||_1-||R_{i+1}||_1$

$R_{i+1} \leftarrow R_{i+1}+dE$

$\delta \leftarrow ||R_{i+1}-R_i ||_1$

while $\epsilon > \delta $

where:

  • $S$ is almost any initial starting vector $\in R^k$, $k>1$ ;

  • $E$ is a fixed vector belonging to $R^k$, $A$ is a fixed matrix of dimensions $k x k$ ;

  • || ||_1 is the $L^1$ norm ;

  • $\epsilon$ is a scalar number for convergence ;

From the article I understand that with this algorithm $R_i$ should converge to the largest eigenvalue of $A+E \times 1^+$ where $1$ is the vector of all ones, but I do not see why. Further, they say that the "$d$ factor maintains $||R||_1$" but I do not see why and in which sense.

MY TRIAL:

For $E=0$, this looks like the power method to find the largest eigenvalue of A. But there is no normalization so I do not understand why $||R||_1$ is "maintened" ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.