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

What changes when a node's disagreement is divided by its degree. For \(L=D-W\) with degrees \(d_i>0\), the **random-walk Laplacian** is

What changes when a node's disagreement is divided by its degree. For L=D−WL=D-WL=D−W with degrees di>0d_i>0di​>0, the random-walk Laplacian is

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

whose action is (Lrwx)i=xi−∑jwijdixj(L_{\mathrm{rw}}x)i=x_i-\sum_j\frac{w{ij}}{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−1D^{-1}D−1 is undefined there.

What is removed and what is kept. Multiplying every weight by c>0c>0c>0 multiplies LLL by ccc but leaves PPP and LrwL_{\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−1LD^{-1}LD−1L is dimensionless: to read it as dynamics in seconds a rate is needed, x˙=−νLrwx\dot x=-\nu L_{\mathrm{rw}}xx˙=−νLrw​x. Normalizing does not preserve the physical clock.

The symmetric version. For W=WTW=W^{\mathsf T}W=WT,

Lsym=D−1/2LD−1/2=I−D−1/2WD−1/2.L_{\mathrm{sym}}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-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=λuL_{\mathrm{sym}}u=\lambda uLsym​u=λu, then v=D−1/2uv=D^{-1/2}uv=D−1/2u satisfies Lrwv=λvL_{\mathrm{rw}}v=\lambda vLrw​v=λv. They do not share the same vector in the same coordinates. LsymL_{\mathrm{sym}}Lsym​ offers Euclidean orthonormal eigenvectors; those of LrwL_{\mathrm{rw}}Lrw​ can be normalized as viTDvj=δijv_i^{\mathsf T}Dv_j=\delta_{ij}viT​Dvj​=δij​. The null modes are 1\mathbf11 for LrwL_{\mathrm{rw}}Lrw​ and D1/21D^{1/2}\mathbf1D1/21 for LsymL_{\mathrm{sym}}Lsym​.

Relation with transition and storage. Since P=I−LrwP=I-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=-D^{-1}Lxx˙=−D−1Lx resembles a capacity proportional to degree, in compatible units; it does not license replacing an arbitrary physical capacity MMM by DDD. 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.

Reference on density and normalization: Nadler, Lafon, Coifman and Kevrekidis, Diffusion maps, spectral clustering and reaction coordinates of dynamical systems (2005)