Jaccard Neighbor Similarity

Problem

Compute the Jaccard similarity of the open neighborhoods of nodes u and v in an undirected graph.

The score is |N(u) intersect N(v)| / |N(u) union N(v)|, or 0.0 when both neighborhoods are empty. edges is a list of [u, v] pairs.

Hint

Jaccard compares shared neighbors against all neighbors of either node.

case 1

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

expected: 0.3333333333333333

case 2

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

expected: 0

case 3

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

expected: 1

case 4

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

expected: 0

Starter codePython

def jaccard_similarity(n, edges, u, v):
    # Your code here
    pass

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