2

In (normal) page rank, the (initial) page rank vector is usually initialized to the uniform distribution.

Should I do the same for personalized page rank? I wonder if I should initialize the page rank vector to the personalized teleportation vector.

In mathematical terms:

pi0 = starting vector at iteration 0 (a row vector)
pi = PageRank vector
H = row-normalized hyperlink matrix (n-by-n sparse matrix)
v = (personalized) teleportation vector (1-by-n row vector)
n = size of H matrix (scalar)
alpha = teleportation prob. (scalar, e.g. 0.85)
epsilon = convergence tolerance (scalar, e.g. 1e-8)

Usually, the starting page rank vector is usually set to the uniform vector:

pi=1/n*ones(1,n).

And then we run the power method:

while (not_converged):
     pi=alpha*pi*H + (alpha*(pi*a)+1-alpha)*v;

My question: should I initialize pi with v? (instead of the uniform vector)

Edit: one further consideration for the implementation is that v is usually quite a sparse vector (unlike the uniform vector pi). Using v might be better in terms of floating-point precision.

Renaud
  • 330
  • 4
  • 12
  • 1
    Mathematically, this should not make a difference, because the PageRank are steady state probabilities of the Google Matrix so they are independent from where you start. From a computational point of view, it does seem sensible to start using the personalised page rank probabilities to reduce number of iterations but I am not too sure about this – tintinthong Aug 29 '17 at 19:09
  • 1
    Can you please provide some relevant reference for the Personalised Page Rank? – usεr11852 Nov 16 '17 at 00:56
  • @usεr11852 Personalized Page Rank (PPR) is the same as PR other than the fact that jumps are back to one of a given set of starting vertices (`v`), instead of the uniform vector. In a way, the walk in PPR is biased towards (or personalized for) this set of starting vertices and is more localized compared to the random walk performed in PR. – Renaud Nov 16 '17 at 08:41
  • @usεr11852 The algorithm is formally described in "Google's PageRank and Beyond: The Science of Search Engine Rankings", 2006, Amy N. Langville, Carl D. Meyer – Renaud Nov 16 '17 at 08:43
  • 1
    Thank you; it makes the question more self-contained! – usεr11852 Nov 16 '17 at 21:56

0 Answers0