1
$\begingroup$

Is there anyway I can calculate the personalized PageRank in R?

A little bit about Personalized PageRank

The Personalized PageRank matrix is defi ned as a n by n matrix solution of the following equation

ppr_alpha = alpha*I + (1-alpha􀀀)*ppr_alpha*M

where alpha is some restart probability and M is a graph given by the n*n random walk matrix. Fixing a node v. The v-th row of the matrix satisfies

ppr_alpha(v,. ) = alpha*e_v + (1-alpha) ppr_alpha(v,. )*M

This is known as the Personalized PageRank (PPR) vector of a node v with restart probability and it was introduced by Haveliwala as the stationary distribution of a random walk on the graph with probability restart at node v after each step.

This is the link to the paper
http://infolab.stanford.edu/~taherh/papers/topic-sensitive-pagerank-tkde.pdf

$\endgroup$
  • $\begingroup$ Take a look to page.rank from igraph. The damping would be 1-alpha in your formula. Hope it helps. $\endgroup$ – lrnzcig Oct 5 '15 at 13:54
  • $\begingroup$ I tried the page.rank function, however I was expecting the page rank to be a square matrix but it returned a single vector. $\endgroup$ – Rajarshi Bhadra Oct 7 '15 at 20:38
  • $\begingroup$ I did not mention in my comment that you need to use the personalized input of page.rank from igraph, I hope you saw that. Anyway, I guess you expect a matrix because each column corresponds to a specific topic? If that's the case, you could execute page.rank once for each of the topics, using the corresponding personalized vector. It should be fast unless your matrix is huge. I don't know of any other implementation. Hope it is clear enough and helpful. $\endgroup$ – lrnzcig Oct 8 '15 at 14:53
  • $\begingroup$ Read through the paper you link to and they actually propose that kind of implementation. First paragraph of 6.1. $\endgroup$ – lrnzcig Oct 8 '15 at 14:57
  • $\begingroup$ I did use the personalized PageRank vector. However I am getting stuck at the using the personalized vector. My code looks something like this page_rank(graph,vids=V(graph),directed=T,damping=.85,personalized = seq(vcount(graph)[i]) but in all cases I am getting the same vector. I am unable to interpret this. Any help will be greatly appreciated $\endgroup$ – Rajarshi Bhadra Oct 8 '15 at 17:42
1
$\begingroup$

After comments, here you have some notes on how to do this in practice. Below I add a very simple example using igraph package in R.

Personalized Page Rank (or Topic-Sensitive Page Rank), does basically the same as Page Rank, however it weights some of the nodes more heavily because of its "topic" (or whatever it applies as personalization in the context of the graph).

In "normal" Page Rank, the random walk through the graph is interrupted with a small probability (the damping parameter) and the walker is sent ("teleported") to a random node of the graph. This random node that the walker jumps to is chosen with a uniform distribution.

In contrast, in personalized Page Rank, the probability of the walker jumping to a node is not uniform, but determined by a certain distribution, which corresponds to the weight of each of the nodes of the graph for the topic.

Since Page Rank is very efficient from a computational point of view, it should be ok, at least as an initial approach, to calculate the rank vector for all the nodes in a loop for each of the topics. In the paper you refer to in your question, they actually do it this way (see paragraph 6.1).

As an example, for a very simple graph (actually the example is taken from the book "Mining of Massive Datasets", which btw has an easily readable explanation on Page Rank and some digressions about how to implement it more efficiently).

g <- graph.formula(A -+ B, A -+ C, A -+ D,
                   B -+ A, B -+ D,
                   C -+ A,
                   D -+ C, D -+ B)

"Normal" Page Rank would be,

> page.rank(g, damping=0.80)$vector
        A         B         C         D 
0.3214286 0.2261905 0.2261905 0.2261905 

The personalized vector, assuming that nodes A and C are not relevant for the topic, and B and D have an equal weight,

> page.rank(g, damping=0.80, personalized=c(0,1/10,0,1/10))$vector
        A         B         C         D 
0.2571429 0.2809524 0.1809524 0.2809524

Where the weight=1/10 is calculated as the probability of jumping to that node, taking into account the decay or damping parameter (i.e. splitting the 0.2 into the two nodes). However, igraph actually normalizes the vector, so you set the total weight of the topic to 1 and divide it among the relevant nodes,

> page.rank(g, damping=0.80, personalized=c(0,1/2,0,1/2))$vector
        A         B         C         D 
0.2571429 0.2809524 0.1809524 0.2809524

leading to the same result. For that matter, you could even set the weights relative to each other,

> page.rank(g, damping=0.80, personalized=c(0,1,0,1))$vector
        A         B         C         D 
0.2571429 0.2809524 0.1809524 0.2809524

Whatever the way you set the numbers, you obtain the vector for the 1st topic. After, you run again for the following topic,

> page.rank(g, damping=0.80, personalized=c(0,1,1,1))$vector
        A         B         C         D 
0.2857143 0.2380952 0.2380952 0.2380952 

Hope it is clear and helpful.

$\endgroup$
  • $\begingroup$ This was an extremely useful and precise explanation that you provided. Just what i needed to understand the concept of personalized pagerank $\endgroup$ – Rajarshi Bhadra Oct 9 '15 at 20:06
  • $\begingroup$ @Irnzcig I used the note you provided to understand personalized page rank. However I am stuck in creating a personalized pagerank matrix as described in this paper (pages.stern.nyu.edu/~narchak/wfp0828-archak.pdf) section 5.2. I tried calculating the personalized PageRank vector for node i (i.e. using node i only as the seed node) with igraph and copying that vector into row i of some matrix - then repeating it for all the nodes. However for a node the sum does not return the page rank as described in the paper. Any help on this will be appreciated. $\endgroup$ – Rajarshi Bhadra Oct 12 '15 at 6:15
  • $\begingroup$ @Irnzcig I have put my exact query in more details here [stats.stackexchange.com/questions/176534/… $\endgroup$ – Rajarshi Bhadra Oct 12 '15 at 8:41
  • $\begingroup$ I'm answering to the other question. Anyway, you basically have to normalize. $\endgroup$ – lrnzcig Oct 12 '15 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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