Cheeger Spectral Cut Bounds
Compare a graph’s best bottleneck cut with its normalized spectral gap.
Free theory articleCompare a graph’s best bottleneck cut with its normalized spectral gap.
Concept & interpretation
Compare a graph’s best bottleneck cut with its normalized spectral gap.
Experiment
Explore spectral clustering guarantees in the Cheeger Spectral Cut Bounds module.
- Change the Graph to Complete and observe how the layout forms a dense K4 topology.
- Notice how the Normalized spectral gap (λ2) jumps to 1.3333333333333333 since highly connected graphs do not have tight bottlenecks.
- Change the Subset mask to 1 (which selects a single node) and verify that the number of cut edges matches the degree of that node, yielding a selected conductance of 0.6666666666666666.
- Switch the graph to Disconnected and witness the spectral gap plummet to exactly 0, confirming there is a cut with no edges.