0
$\begingroup$

I computed the PageRank vector for the example given in https://en.wikipedia.org/wiki/PageRank (where the picture shows that node B ends up with a score of 38.4, node C with 34.3, node D with 3.9). I implemented the PageRank algorithm, but my numbers are slightly different: 39.8 for node B, and 36.1 for node C, 3.5 for node D, etc). I was wondering if anyone could simulate and obtain the same results they have. My question is what algorithm was used to obtain their numbers.

My algorithm is as follows. Starting with the uniform distribution $r$, I did power iteration using the equation $r = Ar$, where $A = 0.85 M + 0.15 J$, $M$ is the transition matrix of the Web graph given in the example, and $J$ is the matrix whose every entry is $1/N$ ($N=11$ is the number of nodes).

$\endgroup$
4
  • 1
    $\begingroup$ You can ask the person who created the image. On the other hand, what do you expect to get out of the answer? There are lots of small choices to be made that could change the final output: Was the system solved by fixed point iteration, or did they solve the system by a direct method (which one)? If they iterated, how many iterations did they do? Did they stop after a predefined number of iterations or after passing a tolerance for the difference between iterations? Which norm was used to compute the difference? $\endgroup$ – plop Aug 11 '20 at 14:54
  • 1
    $\begingroup$ Knowing what options are available as answers for each question above is useful, but which options were used for that specific image ...? It doesn't look like something to care about. $\endgroup$ – plop Aug 11 '20 at 14:57
  • $\begingroup$ How did your algorithm incorporate the PageRank damping factor? $\endgroup$ – Pseudonym Aug 12 '20 at 0:28
  • $\begingroup$ @plop The iterations were done until there was convergence (in the sense that the Euclidean distance between the current vector and the previous one was at most 0.0001). I don't think number of iterations or precision is the reason my answers are slightly different. $\endgroup$ – jm jm Aug 12 '20 at 11:37
0
$\begingroup$

I fixed it and I am now getting the same numbers as in their example. Earlier, I used the equation $r=(0.85M+0.15J)r$ to update $r$, and at the end of each iteration I would scale $r$ so that it sums to $1$. This scaling is necessary because the Web graph can have dead ends, in which case the components of $Mr$ need not sum to 1 even if the components of $r$ sum to 1. Now, I compute the first term $0.85Mr$, and then I redistribute the remaining pagerank (of $1$ minus sum of components of $0.85Mr$) evenly among all the nodes. The latter algorithm distributes the pagerank among all the nodes slightly more uniformly.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.