Personalized PageRank

Problem

Compute personalized PageRank where the teleport mass always returns to a single source node.

Start with all rank on the source. Each round, source gets (1 - d) plus the dangling mass, and every edge passes d * rank_u / out_degree(u) to its target. Iterate until the largest change is at most tolerance (or 1000 rounds). Return the final ranks.

Hint

Replace the uniform teleport vector with a one-hot vector at source.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,0],[2,3]],0,0.85,1e-9]

expected: [0.3472749771422889,0.29518373021944766,0.25090617000328175,0.10663512263498164]

case 2

in: [4,[[0,1],[1,2],[2,0],[2,3]],3,0.85,1e-9]

expected: [0,0,0,1]

case 3

in: [3,[],1,0.85,1e-9]

expected: [0,1,0]

case 4

in: [1,[],0,0.85,1e-9]

expected: [1]

Starter codePython

def personalized_pagerank(n, edges, source, damping, tolerance):
    # Your code here
    pass

4 test cases · run your code against them in the editor