PageRank Convergence Iterations Count

Problem

Count how many PageRank iterations are needed to converge from uniform ranks.

Iterate the standard recurrence with dangling mass redistribution until the largest rank change is at most tolerance, or 1000 iterations pass. Return the number of iterations executed. edges is a list of directed [u, v] pairs.

Hint

A smaller damping factor and a looser tolerance both cut the iteration count.

Test cases

case 1

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

expected: 1

case 2

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

expected: 1

case 3

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

expected: 38

case 4

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

expected: 38

case 5

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

expected: 5

Starter codePython

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

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