SimRank One Iteration

Problem

Perform one iteration of SimRank on a directed graph with n nodes and decay factor c.

Start from the identity matrix: s(a, b) is 1 when a equals b and 0 otherwise. One update sets s(a, a) = 1 and, for a different from b with nonempty in-neighbor sets, s(a, b) = c / (|I(a)| * |I(b)|) times the double sum of the previous similarities over all in-neighbor pairs. Return the resulting n by n matrix. edges is a list of [u, v] pairs.

Hint

Two nodes are similar when their in-neighbors are similar, damped by the factor c.

Test cases

case 1

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

expected: [[1,0,0],[0,1,0.5],[0,0.5,1]]

case 2

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

expected: [[1,0.25,0,0],[0.25,1,0,0],[0,0,1,0],[0,0,0,1]]

case 3

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

expected: [[1,0,0],[0,1,0],[0,0,1]]

Starter codePython

def simrank_one_iteration(n, edges, c):
    # Your code here
    pass

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