Girvan-Newman Remove Max Edge

Problem

Perform one Girvan-Newman step: compute edge betweenness of every edge and remove the single edge with the highest score.

Ties are broken by the normalized endpoint pair with the smallest values. Return the remaining edges as a sorted list of [u, v] pairs with u < v. edges is the input edge list of an undirected graph.

Hint

The bridge between two dense communities carries the highest edge betweenness.

Test cases

case 1

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

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

case 2

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

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

case 3

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

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

Starter codePython

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

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