3
$\begingroup$

Soon I will have an exam where I will be asked to calculate pagerank. So far, I have been thought to use power iteration. However, this can be a very expensive operation to do during an exam, especially when most of the times, the number of nodes is just 3.

Is there any better algorithm to calculate the pagerank of only 3 websites involved?

$\endgroup$
5
$\begingroup$

There is a formula for the PageRank which involves inverting an $n\times n$ matrix. When $n = 3$ this is not too hard. For inverting the matrix, use the formula given on Wikipedia, which is just a special case of the general formula involving the adjugate matrix.

That said, I see absolutely no reason why you would ever have to calculate PageRank by hand. That's what we have computers for. If you are given such an exercise in an exam, the matrix will probably have some very simple structure which will make it easier to handle by hand.

$\endgroup$
  • $\begingroup$ sorry Yuval, I have gone through it again. I think inverting the matrix will lead to yet another linear system to solve. Isn't there any 3x3 property that I am not seeing? $\endgroup$ – revisingcomplexity May 4 '15 at 13:43
  • $\begingroup$ Use the formula here: en.wikipedia.org/wiki/PageRank#Algebraic. When you're inverting a matrix, you're solving a linear system. $\endgroup$ – Yuval Filmus May 4 '15 at 13:48
  • $\begingroup$ Can you give some other hint on that, I am confused how I construct the stochaistic matrix $\endgroup$ – revisingcomplexity May 4 '15 at 13:55
  • $\begingroup$ No, now it's time for you to revise the material on your own. Good luck! $\endgroup$ – Yuval Filmus May 4 '15 at 13:56
  • $\begingroup$ I don't think there is a need for finding the inverse, if I can just use the transpose and solve the linear system. My aim is to avoid that $\endgroup$ – revisingcomplexity May 4 '15 at 14:09
1
$\begingroup$

A less formal answer, but nice step by step strategy is described in this video

$\endgroup$
  • $\begingroup$ After a bit more learning. this is equivalent to solving a linear system $\endgroup$ – revisingcomplexity May 7 '15 at 9:55

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.