which pagerank formula for weighted edges?

[randomgambit]

Hello @gaborcsardi

Thanks for this wonderful, fundamental R package!
I am using igraph via tidygraph to compute the pagerank of nodes in my network.

Unfortunately, I was not able to get the exact mathematical formula you are using to compute the pagerank when edges are weighted. Could you please let me know what you mean by connection strength in

This function interprets edge weights as connection strengths. In the random surfer model, an
edge with a larger weight is more likely to be selected by the surfer

Thanks!

[vtraag]

Assuming the graph is strongly connected (i.e. such that it does not contain any dangling nodes), pagerank is defined as

p_i = alpha sum_j p_j W_ji  + (1 - alpha) e_i

where p_i denotes the pagerank of node i, e is the personalization vector (defaults to 1/n) so that e_i indicates the probability to 'teleport' to node i , alpha denotes the so-called 'damping factor', and W_ji = w_ji/sum_k w_jk, where w_ji is the edge weight from j to i. In other words, W_ji is simply the normalized weight, so that they sum to 1 for all outgoing edges of a node. In the 'random surfer' interpretation, W_ji represents the probability for the 'random surfer' to go to node i from node j, which is simply proportional to the edge weight w_ji.

Does this answer your question? Or do you want to report a specific issue with the pagerank calculations?

[randomgambit]

yes that is pretty clear, thanks a lot! I was not very aware of this definition by iteration. I mostly have seen the pagerank as the steady state vector of the transition matrix

[vtraag]

OK, good! Indeed, the page rank is given by the solution to the recursive equation above.

[randomgambit]

@vtraag actually just a clarification. What happens if the graph is not strongly connected? do you drop the dangling nodes?

[vtraag]

No, they are not dropped. They are assumed to teleport out to the other nodes. In the current release (0.7.1) it is set to the uniform probability, but it is discussed whether that should be done by teleporting out based on the personalization vector instead. See the discussion in this issue #671.

[randomgambit]

got it thanks. so the formula above actually works for the general case as well, right? I can see the teleport probability there

[vtraag]

Well, no, there are two separate teleportation probabilities: one for dangling nodes and one for the personalization. In #671 it is discussed to make them the same, but currently the teleportation probabilities are always set to uniform probabilities for dangling nodes (effectively adding a link to all other nodes for a dangling node). For more details see #671.

[randomgambit]

i ll check it out, thanks!