Fiedler vector

The Fiedler vector is the single best one-dimensional summary of how a connected graph wants to be split in two. It assigns each node a real number such that strongly connected nodes get similar values, so cutting at zero (positives versus negatives) separates the graph along its weakest seam.

Formally, order the Laplacian's eigenvalues 0 = lambda_1 <= lambda_2 <= ... The Fiedler vector is the eigenvector for lambda_2, the second-smallest eigenvalue, called the algebraic connectivity. It is orthogonal to the trivial all-ones eigenvector, so its entries must include both signs, and the sign pattern induces a balanced bipartition.

The value lambda_2 itself measures how well-connected the graph is: it is positive exactly when the graph is connected, and larger values mean the graph is harder to disconnect (a robust, expander-like network), while a near-zero lambda_2 signals a graph with a thin bottleneck waiting to be cut.

Why it matters: the Fiedler vector is the workhorse of graph bisection, mesh and circuit partitioning, and the first step of recursive spectral clustering. The caveat: it gives a relaxation, not the exact minimum cut (which is NP-hard), so the rounded partition is near-optimal rather than guaranteed optimal, and on graphs with several comparable bottlenecks a single vector cannot capture them all.