Personalized PageRank and Random Walks

61 Views Asked by At

I have two questions, each regarding personalized PageRank as provided in a paper I'm reading ("Approximate Personalized PageRank on Dynamic Graphs" by Zhang, Lofgren and Goel; see 1, 2, or 3).


First Question:

The authors give the equation for the personalized PageRank vector $\pi_s$ of a source node $s$:

$$\pi_s = \alpha e_s + (1-\alpha) R \pi_s$$

where $\alpha$ is the teleport probability, $e_s$ is the indicator vector for $s$, and $R$ is the random walk matrix. Would a correct formulation of the personalized PageRank matrix $\pi$ then be

$$\pi = \alpha I + (1-\alpha) R \pi$$

where $I$ is the $n\times n$ identity matrix and $\pi_{s, t}$ is the probability that a random walk from $s$ stops at $t$ given teleport probability $\alpha$? If so, doesn't this not make any sense for $\alpha = 0$ since then we're left with $\pi = R \pi$ and so $R = I$, which is false? What's the correct matrix formulation, or is $a=0$ just not allowed?


Second Question:

Is there any insight on what happens when using powers of $R$? I understand that $R^k_{i, j}$ is the probability of node $i$ landing on node $j$ within $k$ hops. Does this mean using $R^k$ in the personalized PageRank equation corresponds to computing the probability of going from node $s$ to $t$ within $k$ hops with teleport probability $\alpha$?