Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I am trying to implement the PageRank algorithm described in this paper (Fig. 1). Here is the breakdown of the steps:

where:

  • pT is a probability distribution for the random walk (typically, each element is 1/N where N is the total number of elements)
  • P is the connectivity matrix where p(i,j) = {1 or 0} / # outbound links.

I understand the rationale for the first two steps well. In the following equation,

step 2 solves for the second term. However, I don't understand the rationale behind steps 3-4. In particular, I don't see how adding omega * pT in the description of the algorithm amounts to adding (1-d)/N in the equation shown above. As a result, the output I am getting with the two methods differ. Can anybody enlighten me?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

As page 5 of the paper you linked to explains, the random surfer model of the PageRank algorithm interprets one step in the power iteration as a surfer looking at a given page following one of the links with probability $c$ (which of these is determined by their relative weight, i.e., the components of the current iterate $x^k$) and jumping to an unrelated page (e.g., by using a bookmark) with probability $1-c$ (which if these is determined by the components of the vector $p$). As explained, writing this as a matrix-vector product $pA$ with an explicit matrix $A$ is horrendously expensive since jumping to an arbitrary page leads to a fully populated matrix. So one writes $A=cP+(1-c)E$ and calculates $xA = cxP + (1-c)xE$ separately. In the algorithm above, step 2 corresponds to the first term and steps 3 and 4 correspond to the second term. The specific form is derived in detail in the paper (equations (4) and (5)).

Note that the Wikipedia article only includes a uniform jumping probability (confusingly called damping factor), while the paper uses a non-uniform probability (given by the personalization vector $p$) and includes an additional term $D$ to prevent getting stuck on pages without outgoing links.

(I should also remark that the Wikipedia article is not a terribly good explanation of what is going on, especially mathematically. A better source is this SIAM Review article.)

share|improve this answer
add comment

The PageRank method is basically the Power iteration for finding the eigenvector corresponding to the largest eigenvalue of the transition matrix. The algorithm you quote is coming directly from equations (4) and (5) of the paper you reference, and this is just a way of implementing the power iteration for a matrix with a particular structure. I have no idea where your equation involving $ PR(A) $ is coming from or what it means or how it relates to the rest of your question.

share|improve this answer
    
Thanks for your answer. The equation is from the Wikipedia page on PageRank. In this equation, the second term corresponds exactly to y in the outlined algorithm (step 2). I'm having trouble seeing how the rest of step 4 (adding w*pT) in that algorithm corresponds to adding the first term in the second equation. In particular, using these two different methods with the same input results in different results as far as I can tell. –  louism Nov 9 '12 at 14:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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