PageRank with Dangling Mass

Problem

Perform one PageRank power iteration that redistributes dangling mass uniformly.

Start from the uniform distribution over n nodes; nodes with out-degree zero contribute their rank to a dangling pool that is spread evenly across all nodes, while every edge forwards damping * rank[u] / out_degree(u) to its target. edges is a list of directed [u, v] pairs and damping is the damping factor. Return the new rank list.

Hint

Forgetting the dangling pool lets probability mass leak out of the graph.

Test cases

case 1

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

expected: [0.2875,0.7124999999999999]

case 2

in: [3,[],0.85]

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 3

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

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 4

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

expected: [0.1375,0.25,0.25,0.36250000000000004]

Starter codePython

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

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