Edge Prediction Top Pairs

Problem

Rank non-adjacent node pairs by their number of common neighbors and return the top k pairs.

Only pairs with at least one common neighbor are considered. Sort by score descending, then by u and v ascending. edges is a list of [u, v] pairs and each returned pair is [u, v] with u < v.

Hint

Common-neighbor scoring is the simplest edge prediction baseline.

Test cases

case 1

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

expected: [[0,2]]

case 2

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

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

case 3

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

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

case 4

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

expected: [[1,2]]

Starter codePython

def top_predicted_pairs(n, edges, k):
    # Your code here
    pass

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