PageRank One Iteration

Problem

Perform one power iteration of PageRank on a directed graph with n nodes.

Start from uniform ranks of 1/n. For damping factor d, the new rank of i is (1 - d)/n plus d times the rank sent along each incoming edge, where a node splits its rank evenly across its outgoing edges. The rank of dangling nodes (no outgoing edges) is spread uniformly over all nodes. Return the new list of ranks.

Hint

Compute the dangling contribution first, then add each edge's flow into the target node.

Test cases

case 1

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

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 2

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

expected: [0.2388888888888889,0.38055555555555554,0.38055555555555554]

case 3

in: [1,[],0.85]

expected: [1]

case 4

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

expected: [0.3125,0.3125,0.1875,0.1875]

Starter codePython

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

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