PageRank Step

Problem

Perform one PageRank update from rank vector v (which sums to 1) on adjacency matrix A, with damping d.

Build the row-stochastic M where M[i][j] = A[i][j] / row_sum_i, distributing uniformly when a row has no outgoing links. Then return v*M scaled by d plus the teleportation term (1-d)/n in every entry.

Hint

Dangling nodes (no outgoing links) jump uniformly; teleportation keeps the vector summing to 1.

Test cases

case 1

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

expected: [0.5,0.5]

case 2

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

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 3

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

expected: [0.375,0.625]

case 4

in: [[[0,0,0],[0,0,0],[0,0,0]],0.85,[0.3333333333333333,0.3333333333333333,0.3333333333333333]]

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

Starter codePython

def pagerank_step(A, d, v):
    # Your code here
    pass

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