Personalized PageRank Target Mass

Problem

Return the probability mass landing on a target after a fixed number of personalized PageRank steps.

Start with all rank on source; each step sends (1 - damping) plus all dangling mass back to source, and every edge forwards damping * rank[u] / out_degree(u) to its target. Iterate exactly steps times and return rank[target]. edges is a list of directed [u, v] pairs.

Hint

The teleport term keeps returning mass to the source, so nearby nodes accumulate the most.

Test cases

case 1

in: [3,[[0,1],[1,2]],0,2,2,0.5]

expected: 0.25

case 2

in: [3,[[0,1],[1,2],[2,0]],0,2,1,0.5]

expected: 0

case 3

in: [4,[[0,1],[0,2],[1,3],[2,3]],0,1,3,0.85]

expected: 0.06375

case 4

in: [2,[[0,1]],1,1,0,0.5]

expected: 1

case 5

in: [2,[],0,1,2,0.5]

expected: 0

Starter codePython

def ppr_target_mass(n, edges, source, target, steps, damping):
    # Your code here
    pass

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