Calculating Personalized PageRank in R

Question

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

Answer 1

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.