Fiedler value

The Fiedler value (or algebraic connectivity) of a graph is the second-smallest eigenvalue of the graph Laplacian matrix. It is named after Miroslav Fiedler, who proved in 1973 that this eigenvalue is zero if and only if the graph is disconnected, and positive if and only if the graph is connected. The magnitude of the Fiedler value measures how well-connected the graph is: larger values indicate stronger connectivity, smaller values indicate that the graph is close to splitting into separate components. It is the spectral signature of network robustness.

The Fiedler value governs the convergence rate of consensus protocols, the mixing time of random walks, and the quality of spectral clustering partitions. In distributed computing, a small Fiedler value means that information diffuses slowly across the network; a large Fiedler value means fast convergence. In network design, maximizing the Fiedler value is a principled way to ensure resilience against edge failures, because the value itself bounds the number of edges that must be removed to disconnect the network. The Fiedler value is thus a bridge between the continuous mathematics of spectral graph theory and the discrete engineering problem of building robust networks.

The Fiedler value also has a geometric interpretation: it is the minimum of the Rayleigh quotient over all vectors orthogonal to the constant vector, and it measures the 'bottleneck' of the graph — the narrowest constriction through which information must flow. This interpretation connects the Fiedler value to Cheeger's inequality, which bounds the Fiedler value in terms of the graph's isoperimetric number. The connection reveals that spectral connectivity and combinatorial connectivity are two faces of the same structural property: the difficulty of cutting the network into disconnected pieces.