mathematics//graph theory//spectral gap
The spectral gap is the smallest nonzero eigenvalue of a connected network's Laplacian, a number that tells which patterns of the network disappear fast and which reveal weak connections, and in practice it answers how long a network takes to agree: how quickly a sensor network reaches consensus, how fast heat evens out through a structure, how soon a random walk forgets where it started, and where the weak link sits that holds everything back. For a symmetric Laplacian of a connected network the eigenvalues are ordered as follows:
The spectral gap is the smallest nonzero eigenvalue of a connected network's Laplacian, a number that tells which patterns of the network disappear fast and which reveal weak connections, and in practice it answers how long a network takes to agree: how quickly a sensor network reaches consensus, how fast heat evens out through a structure, how soon a random walk forgets where it started, and where the weak link sits that holds everything back. For a symmetric Laplacian of a connected network the eigenvalues are ordered as follows:
0=λ1<λ2≤⋯≤λn,Lvi=λivi.0=\lambda_1<\lambda_2\le\cdots\le\lambda_n,\qquad Lv_i=\lambda_i v_i.0=λ1<λ2≤⋯≤λn,Lvi=λivi.
The mode v1v_1v1 is constant. In x˙=−Lx\dot x=-Lxx˙=−Lx each mode evolves as cie−λitvic_i e^{-\lambda_i t}v_icie−λitvi: the spatial shape is kept and its amplitude shrinks (modes).
Spatial smoothness and temporal speed are the same number. For a unit eigenvector the eigenvalue measures weighted disagreement across the edges:
λi=viTLvi=12∑a,bwab(vi(a)−vi(b))2.\lambda_i=v_i^{\mathsf T}Lv_i=\frac12\sum_{a,b}w_{ab}\bigl(v_i(a)-v_i(b)\bigr)^2.λi=viTLvi=21a,b∑wab(vi(a)−vi(b))2.
A small eigenvalue is a pattern with small differences across strong connections; it may jump across a weak one. Such a pattern is smooth in the weighted geometry of the graph, which need not match the Euclidean closeness of the nodes. A large eigenvalue means more weighted disagreement per unit norm and faster decay in this continuous dynamics.
The gap that governs consensus is λ2\lambda_2λ2, the algebraic connectivity or Fiedler value of the unnormalized Laplacian. It bounds the disagreement with respect to the mean:
∥x(t)−xˉ1∥2≤e−λ2t∥x(0)−xˉ1∥2.\|x(t)-\bar x\mathbf1\|_2\le e^{-\lambda_2t}\|x(0)-\bar x\mathbf1\|_2.∥x(t)−xˉ1∥2≤e−λ2t∥x(0)−xˉ1∥2.
λ2\lambda_2λ2 is zero exactly when the graph is split, and a small value reveals a bottleneck. Four drones in a line have λ2≈0.59\lambda_2\approx0.59λ2≈0.59, and the link that closes them into a ring raises it to 2. Ten in a chain have λ2=2(1−cos(π/10))≈0.098\lambda_2=2(1-\cos(\pi/10))\approx0.098λ2=2(1−cos(π/10))≈0.098, ten that all hear each other have 10, and cutting the disagreement a thousandfold takes ln1000/λ2\ln 1000/\lambda_2ln1000/λ2: about 70 s against 0.7 s for the same algorithm (consensus protocol, spectral reading). The slow scale is 1/λ21/\lambda_21/λ2 when that rate is in physical units and the mode takes part in the state. With unequal capacities the generalized problem Lv=λMvLv=\lambda MvLv=λMv is used, not just the spectrum of LLL. Absolute values of λ2\lambda_2λ2 must not be compared while ignoring the weight scale: multiplying every weight by a hundred multiplies the rates without changing which nodes are connected.
ε0.30 λ20.134 slow time 1/λ27.4 λ34.000 Two groups held together by edges of weight ε. The spectrum of L is (0.00, 0.13, 4.00, 4.00, 4.00, 4.00, 4.00, 4.47): the disagreement inside a group dies at rate λ3 or faster, the one between groups at λ2, and λ2 goes to zero with ε.
Slide the bridge weight toward zero and play: λ2 sinks toward the origin of the spectrum and the disagreement between the groups flattens along its bound, while a split inside one group still dies at once.
The normalized Laplacian relates the spectra; the stationary distribution and the mixing of a random walk are the probabilistic reading of persistence; spectral clustering exploits the separation between scales.
?Does the same eigenvalue mean the same speed in a random walk?
Not necessarily. In P=I−LrwP=I-L_{\mathrm{rw}}P=I−Lrw a mode has per-step factor μi=1−λi\mu_i=1-\lambda_iμi=1−λi. A μ\muμ near one is persistent without alternation; a μ\muμ near minus one is also persistent but alternates in sign. An eigenvalue of LrwL_{\mathrm{rw}}Lrw near two can therefore be a slow alternation in a discrete walk even though that same value gives fast decay in the normalized continuous diffusion. The relevant gap for reversible discrete mixing is 1−maxi≥2∣μi∣1-\max_{i\ge2}|\mu_i|1−maxi≥2∣μi∣. A lazy walk Plazy=(I+P)/2P_{\mathrm{lazy}}=(I+P)/2Plazy=(I+P)/2 adds a probability of staying and removes the bipartite alternation; its eigenvalues then lie in [0,1][0,1][0,1]. See discretization.