Spectral Clustering Cut Value

Problem

Given an undirected graph adjacency matrix A and a labeling of its vertices with 0 or 1, return the cut value: the sum of edge weights between vertices with different labels.

Count each undirected edge once.

Hint

A smaller cut for the same partition sizes indicates a stronger cluster structure.

Test cases

case 1

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

expected: 2

case 2

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

expected: 1

case 3

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

expected: 2

case 4

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

expected: 0

Starter codePython

def cut_value(A, labels):
    # Your code here
    pass

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