mathematics//graph theory//graph Laplacian//normalized Laplacian

The normalized Laplacian is a version of the graph Laplacian that divides each node's disagreement by its degree, so that it keeps the relative connectivity of a graph and drops the global scale of its weights, and spectral clustering uses it to define a grouping geometry. For \(\cc{L}=\cb{D}-\ca{W}\) with degrees \(\cb{d_i}>0\), the **random-walk Laplacian** is

The normalized Laplacian is a version of the graph Laplacian that divides each node's disagreement by its degree, so that it keeps the relative connectivity of a graph and drops the global scale of its weights, and spectral clustering uses it to define a grouping geometry. For L=D−W\cc{L}=\cb{D}-\ca{W}L=D−W with degrees di>0\cb{d_i}>0di​>0, the random-walk Laplacian is

Lrw=D−1L=I−P,P=D−1W.\cc{L_{\mathrm{rw}}}=\cb{D}^{-1}\cc{L}=I-P,\qquad P=\cb{D}^{-1}\ca{W}.Lrw​=D−1L=I−P,P=D−1W.

The Laplacians in copper, the degrees in blue, the weights in green. Its action is (Lrwx)i=xi−∑jwijdixj(\cc{L_{\mathrm{rw}}}x)_i=x_i-\sum_j\frac{\ca{w_{ij}}}{\cb{d_i}}x_j(Lrw​x)i​=xi​−∑j​di​wij​​xj​. It no longer measures an absolute sum of differences but the difference with respect to the weighted mean of the neighbors; the coefficients of that mean sum to one. Zero degree demands an explicit decision (separate isolated nodes or adopt a convention): D−1\cb{D}^{-1}D−1 is undefined there.

Normalizing removes the global scale and keeps relative connectivity. Multiplying every weight by c>0c>0c>0 multiplies L\cc{L}L by ccc but leaves PPP and Lrw\cc{L_{\mathrm{rw}}}Lrw​ unchanged: the global intensity scale goes, relative connectivity stays. That does not erase every influence of sampling density. Density, choice of neighbors, affinity width and geometry still shape the graph. A density-free operator needs extra hypotheses and normalizations, as the diffusion-maps analysis by Nadler, Lafon, Coifman and Kevrekidis shows (reference in the last bullet). If the weights were conductances with units, D−1L\cb{D}^{-1}\cc{L}D−1L is dimensionless: to read it as dynamics in seconds a rate is needed, x˙=−νLrwx\dot x=-\nu \cc{L_{\mathrm{rw}}}xx˙=−νLrw​x. Normalizing does not preserve the physical clock.

For a symmetric W=WT\ca{W}=\ca{W}^{\mathsf T}W=WT there is also a symmetric version:

Lsym=D−1/2LD−1/2=I−D−1/2WD−1/2.\cc{L_{\mathrm{sym}}}=\cb{D}^{-1/2}\cc{L}\cb{D}^{-1/2}=I-\cb{D}^{-1/2}\ca{W}\cb{D}^{-1/2}.Lsym​=D−1/2LD−1/2=I−D−1/2WD−1/2.

Both normalized Laplacians share the spectrum because they are similar: if Lsymu=λu\cc{L_{\mathrm{sym}}}u=\lambda uLsym​u=λu, then v=D−1/2uv=\cb{D}^{-1/2}uv=D−1/2u satisfies Lrwv=λv\cc{L_{\mathrm{rw}}}v=\lambda vLrw​v=λv. They do not share the same vector in the same coordinates. Lsym\cc{L_{\mathrm{sym}}}Lsym​ offers Euclidean orthonormal eigenvectors; those of Lrw\cc{L_{\mathrm{rw}}}Lrw​ can be normalized as viTDvj=δijv_i^{\mathsf T}\cb{D}v_j=\delta_{ij}viT​Dvj​=δij​. The null modes are 1\mathbf11 for Lrw\cc{L_{\mathrm{rw}}}Lrw​ and D1/21\cb{D}^{1/2}\mathbf1D1/21 for Lsym\cc{L_{\mathrm{sym}}}Lsym​.

The normalized Laplacian is tied to the transition matrix, and only loosely to storage. Since P=I−LrwP=I-\cc{L_{\mathrm{rw}}}P=I−Lrw​, right eigenvectors coincide and eigenvalues relate by μ=1−λ\mu=1-\lambdaμ=1−λ. But a column distribution of probabilities evolves through PTP^{\mathsf T}PT (Markov chain). Writing x˙=−D−1Lx\dot x=-\cb{D}^{-1}\cc{L}xx˙=−D−1Lx resembles a capacity proportional to degree, in compatible units; it does not license replacing an arbitrary physical capacity MMM by D\cb{D}D. Those are different decisions (nodal capacity).

The spectral gap separates continuous rates from discrete per-step factors; spectral clustering uses these normalizations to define a grouping geometry.

Density and normalization are treated in Nadler, Lafon, Coifman and Kevrekidis, Diffusion maps, spectral clustering and reaction coordinates of dynamical systems (2005).