Power iteration method in IGPersonalizedPageRank[]?

Hi all!

New to discourse, so sorry if this isn’t the right format. For some specific application, I need to perform the Power Iteration method to find the stationary distribution of a random walk on a graph. I found that it is possible, but not recommended, to perform this method in IGPersonalizedPageRank[]. Will this be available in the future? Why is it deprecated?

I can in fact run it (just doing IGPersonalizedPageRank[myGraph, myNode, myDecayParam, Method -> "PowerIteration"]), and I get a result, but I also get some errors:

As a side note, the result I get with this code differs from the result I get with no method specified. Also, my graph edges have no weights, so the error about weights is weird, is this referring to the edge weights? As I said, what I need for my application is the “intermediate” steps in the iteration process, so that’s the reason I would be interested in having this method implemented, as well as an option to allow for edge weights (even though in my current examples edges have no weights, I could use that in the future).

In summary, I would like to know if it is planned to implement/improve/curate the iteration method. Also, I would appreciate some intuition behind the sub-options usage (Number of Iterations, and Epsilon). I understand Epsilon is some threshold for convergence, so, is it necessary to give both parameters or one/the-other?

Thanks!

Welcome to the igraph forum! Discourse is just the platform we use: this is a normal discussion forum and there are not so many strict rules as on StackExchange (which does not allow discussion).

No, this method will be removed from the next version of IGraph/M. I has been removed from igraph’s C core a while ago.

Because the other two available methods are superior in robustness, speed, and capability (for example, they support weights and personalization).

These are warnings, not errors.

The first one, saying that the graph is weighted, was a bug in igraph’s C core. It should have said that personalization is not supported by this method, and the personalization vector will be ignored.

You did not actually say this before, and it’s not clear to me what you mean. What do you mean by “intermediate steps” and why can’t you use the other two methods?

No, it is not. Can you explain why you can’t use the other methods?

P.S. As I said to you on StackExchange, in IGraph/M 0.5, the PageRank calculation had some bugs which would be triggered under very specific conditions. I will list these here:

  • Wrong results with the PRPACK (i.e. default) method if the graph is not strongly connected and a non-uniform personalization vector was given. If both of these conditions are true, use the Arnoldi method.
  • The Arnoldi method ignored self-loops.
  • Wrong results with the PRPACK method when the graph was weighted, it had fewer than 128 vertices, and it has paralell edges. Use the Arnoldi method for multigraphs (assuming you don’t have self-loops).

As you can see, these are rather specific situations that do not affect more use cases. I fixed all of these in the C core and the fixes will be in the next version of IGraph/M.

P.P.S. LinkRank, which you requested, will also be included in the next version.

Thank you! The methods implemented work great, so that’s not the issue. It is more of a specific need. In order to test many values of the damping factor for the personalized page rank, there’s a method that takes advantage of the page ranks computed at each iteration, using a single value of the damping factor as a “reference”. The ultimate purpose is calculating the “Total Page Rank”, which can be thought of as the personalized page rank over all possible damping values (0, 1), but obtained without actually calculating them, only through the convergence of the single value chosen as the “reference”. The method is mainly presented/described in this and this papers. I hope this makes sense, I’m also learning along the way about this methods.

P.S. Maybe it would be cool implementing some IGTotalPersonalizedRank[], if it is not that hard, but I don’t know if here’s where we request features.

P.P.S. Also, thank you for LinkRank[]!

Feel free to request this feature here (click “New Issue”), and please do mention that it’s for IGraph/M.

1 Like