Spectral Clustering Fiedler Signs

Problem

Partition a connected undirected graph into two spectral clusters by the sign pattern of the Fiedler vector.

Build the Laplacian, compute its eigenvectors with the Jacobi rotation method, take the eigenvector of the second smallest eigenvalue, and return +1 for entries at least 0 and -1 otherwise. edges is a list of [u, v] pairs and n is small.

Hint

The Fiedler vector changes sign exactly where the graph is best cut in two.

Test cases

case 1

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

expected: [1,1,-1,-1]

case 2

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

expected: [1,1,1,-1,-1,-1]

case 3

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

expected: [1,-1,1]

Starter codePython

import math
def fiedler_signs(n, edges):
    # Your code here
    pass

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