PageRank Iterate to Tolerance

Problem

Iterate the PageRank recurrence until the largest rank change between two rounds is at most tolerance (or 1000 rounds pass).

Start from uniform ranks 1/n. With damping d, each node keeps (1 - d)/n of the teleport mass, dangling nodes spread their rank uniformly, and every edge passes d * rank_u / out_degree(u) to its target. Return the final rank list.

Hint

Track the maximum absolute change and stop as soon as it fits the tolerance.

Test cases

case 1

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

expected: [0.3693235345111402,0.2045815501752522,0.3784758676945599,0.04761904761904763]

case 2

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

expected: [0.08118361651499265,0.15018969072346783,0.20884485377079753,0.25870174205376656,0.30108009693697546]

case 3

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

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 4

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

expected: [1]

Starter codePython

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

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