4
$\begingroup$

I'm using Szabolcs' IGraphM to calculate the personalized Page rank for each node in a graph. I was wondering about the 'reset' parameter, what exactly is it? enter image description here

As I understand, the personalized Page rank has one (or more) relevant/'personalized' vertex, from which the probability of reaching other vertices in a random walk is calculated (with some damping factor if needed). The second argument for IGPersonalizedPageRank asks for a vector equal in length to the number of vertices in the graph. What goes into this vector?

Dummy example, where I simply placed a binary vector as the 'reset':

<< IGraphM`

dampFactor = 0.5;
g = RandomGraph[{5, 5}]

enter image description here

IGPersonalizedPageRank[g, {0,0,0,1,0}, dampFactor]
(*{0.150943, 0.169811, 0.0377358, 0.603774, 0.0377358}*)

It seems to me that what the vector contains is a probability vector of resetting a random walk onto the corresponding vertex? (corresponding to the position in the vector). But I've also added non-binary vectors (positive integers, for instance), and it still gives an output with no complaints, maybe in these cases it simply rescales the probability vector?

Thanks!

$\endgroup$
1
  • $\begingroup$ Aha! In the documentation for igraph in R, when setting personalized = True in page_rank(), the option is an "Optional vector giving a probability distribution to calculate personalized PageRank. For personalized PageRank, the probability of jumping to a node when abandoning the random walk is not uniform, but it is given by this vector. The vector should contains an entry for each vertex and it will be rescaled to sum up to one." I will presume this is the case here too, but will leave the question open for now. $\endgroup$ Feb 20, 2021 at 3:10

1 Answer 1

9
$\begingroup$

It seems to me that what the vector contains is a probability vector of resetting a random walk onto the corresponding vertex?

Yes, an un-normalized probability vector.

Introduction to PageRank

The PageRank score is based on the idea of a web surfer randomly clicking through links, i.e. a random walk on the directed graph of webpages and links.

After each step of the random walk, there is a probability $d$ to continue with the walk. $d$ is called the damping factor. With probability $1-d$, the walker jumps to a random vertex in the graph, and restarts the walk from there. The PageRank score of a vertex is the fraction of time the walker spent in that vertex after having continued this process for a very long time.

The "personalization vector", called reset in this implementation, allows controlling which vertex the walk is restarted from. When the walker restarts (with probability $1-d$ in each step), it will choose vertices with probabilities proportional to the corresponding entry in the reset vector.

Note that the entries of the reset vector do not need to sum to 1. They will be normalized to proper probabilities automatically. This is convenient for the very common application when we always want to restart the walk from a specific vertex (or a few specific vertices).

Example:

g = IGSquareLattice[{10, 10}, VertexSize -> Large];
reset = ReplacePart[
   ConstantArray[0, VertexCount[g]], {{29}, {74}} -> 1];

g // IGVertexMap[ColorData["Rainbow"], 
  VertexStyle -> (IGPersonalizedPageRank[#, reset, 0.95] & /* Rescale)]

enter image description here

Here I chose to always restart the walk from either the 29th or 74th vertex of the graph. I set their weight to 1 and all the other weights to 0.

Subtleties in interpretation: getting stuck in sink vertices

It is good to note that there are subtleties with PageRank (and various implementations tend to differ in these). PageRank is mainly useful for directed graphs. In the undirected case, it is somewhat trivial: as the damping factor approaches 1, the PageRank scores approach the degrees.

But with directed graphs, the random walk may get stuck in a vertex which has no outgoing edges. The intention with igraph's implementation was that when this happens, the walk should also be restarted from a vertex chosen with probabilities reset. However, there was a bug: when using the PRPACK method, stuck walkers were actually restarted from a uniformly chosen vertex. The ARPACK method did not suffer from this bug (but is it less reliable and slower than PRPACK).

This bug is present in IGraph/M 0.5.1. I fixed it in the C core of igraph recently, the fix is in igraph 0.9.0 (released a few days ago), and it will of course also be in IGraph/M 0.6 (to be release soon, maybe 2 weeks?). Until then, you can use the ARPACK method. Note that the bug is only triggered when: (1) the graph is not (strongly) connected, so walkers can get stuck (2) you set a non-uniform personalization vector. When the walk is restarted due to damping (and not due to getting stuck), the reset vector is always respected.

Relation to the built-in PageRankCentrality

The built-in PageRankCentrality works the same way as the one in IGraph/M, with the following differences:

  • The syntax is PageRankCentrality[graph, damping, reset].
  • The reset vector must be normalized, i.e. its elements must sum to 1.
  • reset may be a scalar, in which all elements are assumed to be the same. This is somewhat pointless, as the only valid value is 1/VertexCount[g].
  • It is not documented that the default damping is 0.85, but that is indeed what it is (according to experimentation). It'd be difficult to find this out if we didn't have IGraph/M's version to compare to ...
  • PageRankCentrality ignores self-loops. IGPageRank and IGPersonalizedPageRank do not.
  • As of M12.2, PageRankCentrality does not support weighted graphs. IG(Personalized)PageRank does.

Changes planned for IGraph/M 0.6

Update: This change is now released.

Given that restarting from a specific vertex is a common use case, I am also planning to make another change in IGraph/M 0.6: it will be possible to give the reset argument as an association from vertex names to weights. So, if you want to always restart the walk from vertex "a" or "b", having twice the probability for "a" than "b" and zero for the rest of the vertices, the following will work

IGPersonalizedPageRank[g, <|"a" -> 2, "b" -> 1|>]

I did not make this change yet, so now is the time to give feedback on the idea.

$\endgroup$
10
  • 1
    $\begingroup$ PageRank is the fraction of time spend in a node after "a long time", i.e. "a large number of restarts". There is no difference between the initial starting node and the "restarting" node. I hope I understood what you were asking @TumbiSapichu. $\endgroup$
    – Szabolcs
    Feb 21, 2021 at 10:02
  • 1
    $\begingroup$ @TumbiSapichu Yes, correct in both cases. When always returning to the same node, a damping factor of 0 gives 1 for that node and zero for the rest. (More generally: a damping factor of 0 returns the personalization vector.) With a damping factor of 1, and a connected graph (either directed or undirected), the personalization doesn't matter as the walk is never restarted. With a damping factor of 1, and a connected undirected graph, the PageRank scores are simply proportional to the degrees. $\endgroup$
    – Szabolcs
    Feb 22, 2021 at 6:47
  • 1
    $\begingroup$ @TumbiSapichu Damping factor values of precisely 0 and precisely 1 can be a problem for the computation algorithms used by this function. Therefore, 0 was disallowed. In the new version, 0 will work fine, but 1 probably won't, at least not with the PRPACK method (with Arnoldi it should do better). I'll look into whether the behaviour of 1 can be improved, but no promises. Values like 0.0001 or 0.9999 should be safe to use. $\endgroup$
    – Szabolcs
    Feb 22, 2021 at 6:52
  • 1
    $\begingroup$ @TumbiSapichu Keep the feedback coming, and for a longer discussion consider using igraph.discourse.group $\endgroup$
    – Szabolcs
    Feb 22, 2021 at 6:53
  • 1
    $\begingroup$ @TumbiSapichu OK, I implemented it (I assume you wanted the weighted case, which Mma's built-in doesn't support). However, SE is not meant for discussion so please direct detailed feature requests to either the issue tracker on GitHub or to the igraph forum $\endgroup$
    – Szabolcs
    Feb 22, 2021 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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