I'm trying to implement PageRank. I'm reading the description here: http://nlp.stanford.edu/IR-book/html/htmledition/markov-chains-1.html

enter image description here

Everything is very clear to me, however I'm concerned about the construction of the matrix $P$. I find that constructing $P$ the naive way would be very expensive. For example: to implement step 1, one would need to check every row of $A$ and then check every element of that row to see if all elements are zero. For step 2 one would need to compute the number of ones for each row. I can imagine my code to have nasty slow loops. I was wondering if there are smart linear algebra techniques that could efficiently construct $P$. I will be using python numpy for my coding.

EDIT: one way I'm thinking now to solve this is by doing a summation element wise over the columns of $A$. By that I would have a column vector. Now I will go through each element of this vector to check which elements are zeros. Thus I can now know which rows has no 1s and I can multiply those rows with $1/N$.

  • 2
    $\begingroup$ Depending on what you're trying to do, you may not want to explicitly construct $P$. If you can write a function that calculates the matrix-vector product $Px$, given any vector $x$, that may be good enough (or even preferable). $\endgroup$ – Geoff Oxberry May 7 '14 at 0:30
  • $\begingroup$ You can find many Matlab-Implementations of PageRank, which should straightforwardly translate to numpy. $\endgroup$ – Christian Waluga May 7 '14 at 7:17

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.