Implementing PageRank using the Power Method

Question

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

http://www.louismullie.com/algo.png

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?

Answer 1

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.)

Answer 2

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.