Normalized Cut Lite

Problem

Compute the normalized cut value of a two-way partition of an undirected graph.

Let A be the community of node 0 and B all remaining nodes. With cut the number of crossing edges and vol the sum of degrees in a side, the value is cut / vol(A) + cut / vol(B); return 0.0 when either volume is zero. edges is a list of [u, v] pairs and community maps each node to a label.

Hint

Normalizing by volumes penalizes cuts that isolate a tiny set of nodes.

Test cases

case 1

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

expected: 0.2857142857142857

case 2

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

expected: 0.6666666666666666

case 3

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

expected: 0

case 4

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

expected: 1.3333333333333333

case 5

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

expected: 2

Starter codePython

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

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