PageRank

Problem

Run the iterative PageRank algorithm on a directed graph.

edges is a list of [from, to] pairs and num_nodes is the node count. Initialize every rank to 1/num_nodes and repeat the given number of iterations: each node splits its rank equally across outgoing links, dangling nodes spread their rank across all nodes, and every node receives (1 - damping) / num_nodes as a base. Use damping=0.85 by default and return the final rank list; an empty graph returns [].

Hint

Compute the next rank vector from the previous one; never update in place.

Test cases

case 1

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

expected: [0.20153086419753088,0.347054012345679,0.45141512345679013]

case 2

in: [[[0,1]],2,0.85,5]

expected: [0.34880948730468747,0.6511905126953125]

case 3

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

expected: [0.1975828206588288,0.2815526116649371,0.5208645676762342]

case 4

in: [[],0,0.85,3]

expected: []

Starter codePython

def pagerank(edges, num_nodes, damping=0.85, iterations=10):
    # Your code here
    pass

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