Spectral Clustering with a Fiedler Cut

Spectral clustering uses the eigenvalues and eigenvectors of graph matrices to partition nodes. In this module, we examine a simple path graph of four nodes with a variable bridge weight to see how the graph structure is embedded into a one-dimensional line using the Fiedler vector (the eigenvector corresponding to the second smallest eigenvalue of the unnormalized Laplacian matrix), and how this embedding determines a two-way cut.

Experiment

We can visualize how the algebraic connectivity and partition change interactively. Follow these steps to observe the calculation in action:

1. Open the Spectral Clustering with a Fiedler Cut module.
2. Set the Bridge weight to 1. Notice that the graph is now a uniform path. The second eigenvalue increases to roughly 0.585786, and the normalized cut score becomes 0.666666.
3. Change the Bridge weight to 0. The graph is now disconnected into two components (0-1 and 2-3). The second eigenvalue is exactly 0.0, representing this disconnection. The algorithm gracefully handles the multiple zero eigenvalue by picking a chosen component basis.
4. Select a different Vertex, like 3, and observe its coordinate on the Fiedler vector embedding. It mirrors Vertex 0's magnitude but with the opposite sign.