Is there any PageRank-like method on weighted graph?

Question

I found that PageRank algorithm depend heavily on the existence of edges, but the weights of edges give small effect. For example, PageRank on triangle graph(A -> B, B -> C, C -> A) is always (1/3, 1/3, 1/3) even if one of the weight is 0.0000001. Is there any PageRank-like method work well on the weighted graph?

Thanks in advance!

Answer 1

Weighted versions of Pagerank do exist, and it is easy to incorporate edge weights into the PageRank algorithm (just multiply each edge's probability by its weight vector, and then normalize to make the edge probabilities to add up to 1)

The difficult question is how to set these weights. Backstrom and Leskovec propose an algorithm to learn these weights in their WSDM paper on Supervised Random Walks which they propose for use in link prediction and link recommendation.

Answer 2

As you mentioned, PageRank is effective to identify important nodes in the connected graphs.

I think you need to think about what kinds of weights to add, and where you put the weight on.

I found several works adding weights on edges.

• inbound/outbound link weighted PageRank (Xing, Ghorbani 2004)
• AuthorRank considering link weights among the co-authorship links (Liu, Bollen, Nelson, and Sompel 2005)

And, some other works adding weights on nodes.

• a credit-weighted PageRank (Radicchi, Fortunato, Makines, Vespignani 2009)
• a weighted PageRank with number of citation, number of publication (Ding 2011)

Answer 3

In the specific example you mentioned, the weight will indeed not matter.
In your example of a triangle graph (A->B, B->C, C->A), every node has a link to exactly one other node.

The PageRank algorithm normalizes the adjacency matrix by the number (or total weight) of edges. The probability to go from node i to node j depends on the weight of the edge e_ij divided by the sum of weights of edges going out from node i.
So, if a node has only one outgoing edge, it doesn't matter what's its weight is.

(Of course, one can imagine a variant where the 'damping factor' is dependent on the total weight of node edges, so that when that sum is low, the probability of ending the walk is high).