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?
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).
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.
@szhorvat Thanks for the update, it seems great! I have a question about the personalized link rank. In the documentation, it says:
The LinkRank of edges can be computed from the PageRank by simply dividing the PageRank of each vertex between its outgoing edges, proportionally with their edge weights. The LinkRank scores of the out-edges of a vertex add up to the PageRank of that vertex. The LinkRank scores of all edges in the graph add up to 1.
Say I have nodes A and B in some graph G. They are joined by edge E_ab, in an undirected, unweighted graph, and also joined to other nodes (not of interest for this discussion).
If I compute a personalized node rank from A to all other nodes, there will be some weight associated to B at the end (and to A). Then, computing the personalized E_ab would be: rank of A divided by its degree? What about the contribution of B? Isn’t it the “total” edge rank the sum of weight of A/A-degree + weight of B/B-degree? Like, the E_ab edge can be reached via A or B. Just to understand the docs, which seem to imply that it suffices computing this from either A or B, in this case. I hope that’s clear. Thanks!
The description in the in the documentation applied to directed graphs, which is the main use case for PageRank.
Undirected graphs are treated as if each undirected edge were two directed ones running in opposite directions. Then the LinkRank of an undirected edge is the sum of the LinkRanks of its two constituent directed edges.
Here is an example, which converts an undirected graph to directed, computes the LinkRank, then sums up the LinkRanks of reciprocal edges. This yields the same as the LinkRank computation on the undirected graph.
@szhorvat Ok, cool! But is it my intuition correct that if I get a personalized page rank from some node in an undirected graph, then I can get all the link ranks by the sum of their connected node ranks, each divided by their degree? Just trying to avoid converting to directed/undirected and do it directly.
