归一化拉普拉斯矩阵

归一化拉普拉斯矩阵（normalized Laplacian matrix）在图拉普拉斯矩阵两侧按顶点度的平方根缩放，使谱描述相对于度数的差异。整体倍增边权不会改变这个矩阵，但改变不同顶点之间的相对权重通常会改变它。

路径的零向量发生了变化

无权路径 $1-2-3$ 的度为 $(1,2,1)$。它的对称归一化拉普拉斯为 $$ℒ=\left(\begin{array}{ccc}1& -1/\sqrt{2}& 0\\ -1/\sqrt{2}& 1& -1/\sqrt{2}\\ 0& -1/\sqrt{2}& 1\end{array}\right).$$ 与未归一化矩阵相比，中心点与两端的缩放不同。常数向量不再落在核中；正确的零特征向量是 $(1,\sqrt{2},1{)}^{𝖳}$。将它代回第一行得到 $1-\sqrt{2}/\sqrt{2}=0$，其他行也为零。

顶点度不同时，核向量的分量随平方根度变化。归一化没有把所有顶点都赋相同分量。

定义包含孤立顶点的约定

设图有限、无向、无自环、边权非负。记 $L=D-A$，定义对角矩阵 R：当 $d_i>0$ 时 $R_{ii}=d_i^{-1/2}$，当 $d_i=0$ 时 $R_{ii}=0$。本文采用 $$ℒ=RLR.$$ 若所有度都正，这就是 $D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}$。

有孤立顶点时，最后的单位矩阵必须改为只在正度顶点上取一的对角矩阵 $I_{+}$：$ℒ=I_{+}-RAR$。孤立顶点对应的对角元为零，整行整列为零。若机械地使用全体顶点上的 $I-RAR$，孤立点的对角元会误成一，零空间和谱都会改变；这不是同一个约定。

记 E 为正权边集。令 $y_i=x_i/\sqrt{d_i}$ 对正度顶点成立，孤立处令 $y_i=0$。代入 L 的能量公式可得 $$x^{𝖳}ℒx=\sum _{\{i,j\}\in E}{w}_{ij}{(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}})}^2.$$ 边的端点必有正度，所以式内没有除零。它是归一化后的差值平方和，仍非负。

零空间与全部谱的范围

对每个含边的连通分量，能量为零等价于 $x_i/\sqrt{d_i}$ 沿所有正权边保持同一常数，因此该分量的核由平方根度向量张成。每个孤立顶点又独立贡献一个坐标方向。由此，本文约定下零特征值的重数仍等于连通分量数。

所有特征值还位于 $[0,2]$。下界已由能量非负证明。对上界，逐边用 $(a-b{)}^2\le 2(a^2+b^2)$： $$x^{𝖳}ℒx\le 2\sum _{i:d_i>0}\frac{x_i^2}{d_i}\sum _j{w}_{ij}=2\sum _{i:d_i>0}{x}_i^2\le 2x^{𝖳}x.$$ 在中间求和只包含正度顶点。取特征向量代入就得到对应特征值不超过二，这给出了完整上界证明。

主例中另外两个向量 $(1,0,-1{)}^{𝖳}$ 与 $(1,-\sqrt{2},1{)}^{𝖳}$ 分别对应特征值一、二；加上前面的核向量，三向量正交，故谱恰为 $0,1,2$。上界二可以实际达到，并非一个永远取不到的估计。

整体尺度与随机游走的联系

把主例全部边权乘七，A、D、L 都乘七，而 R 的正度部分乘 $1/\sqrt{7}$，两侧抵消后 $ℒ$ 不变。作为变式，若加入一个孤立点，谱则变为 $0,0,1,2$；整体缩放与增加分量是不同操作。

当所有度正时，令 $P=D^{-1}A$。每行求和为一，P 可以表示以边权为比例选择下一邻点的随机游走。随机游走拉普拉斯 $L_{\mathrm{r}\mathrm{w}}=I-P$ 一般不对称，但 $$ℒ=D^{1/2}{L}_{\mathrm{r}\mathrm{w}}{D}^{-1/2}.$$ 所以它与对称矩阵相似，特征值相同；对应特征向量需同时变换，不能直接照抄。孤立点的游走规则要另外约定，不能用未定义的 $D^{-1}$。这里的相似关系只用于正度部分。

对正度图，换元 $x=D^{1/2}y$ 使瑞利商成为 $$\frac{x^{𝖳}ℒx}{x^{𝖳}x}=\frac{y^{𝖳}Ly}{y^{𝖳}Dy}.$$ 分母按度加权，零方向的正交条件为 $\sum _i{d}_i{y}_i=0$。这正是它与图的导通率相配的原因；未归一化的代数连通度使用普通平方和分母，回答的是另一种尺度的问题。