mathematics//graph theory//spectral gap
Which patterns disappear fast and which reveal weak connections. For a symmetric Laplacian of a connected network,
Which patterns disappear fast and which reveal weak connections. For a symmetric Laplacian of a connected network,
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. For a unit eigenvector,
λ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. "Smooth" refers to the weighted geometry of the graph, not necessarily to 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. λ2\lambda_2λ2 is the algebraic connectivity or Fiedler value of the unnormalized Laplacian. For 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.
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.
The discrete warning. 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.
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.