Node2Vec Transition Probabilities Lite

Problem

Compute the unnormalized node2vec transition weights from prev to each neighbor of cur.

The weight is 1/p when the neighbor equals prev, 1 when the neighbor is adjacent to prev, and 1/q otherwise. edges is a list of [u, v] pairs. Return a list of [neighbor, weight] pairs sorted by neighbor.

Hint

The return parameter p and in-out parameter q trade off backtracking against exploration.

Test cases

case 1

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

expected: [[0,1],[2,1],[3,1]]

case 2

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

expected: [[0,0.5],[2,2],[3,2]]

case 3

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

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

Starter codePython

def node2vec_probs(n, edges, prev, cur, p, q):
    # Your code here
    pass

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