图 Laplacian

形式陈述 ​

设 $G=(V,E,w)$ 是有限无向图，每条边 $\{u,v\}$ 有非负权重 $w_{uv}$；无权图取 $w_{uv}=1$。加权邻接矩阵 $A$ 满足 $A_{uv}=w_{uv}$，度矩阵 $D$ 是对角矩阵，$D_{uu}=d_u=\sum _v{w}_{uv}$。图的组合 Laplacian 定义为

$$L=D-A.$$

对任意 $x\in {\mathbb{R}}^V$，对称性给出

$$x^{\mathsf{T}}Lx=\sum _{\{u,v\}\in E}{w}_{uv}(x_u-x_v{)}^2\ge 0.$$

因此 $L$ 是实对称半正定矩阵。每行元素之和为零，所以 $L\mathbf{1}=0$；更一般地，$Lx=0$ 当且仅当 $x$ 在每个连通分量上为常数。由此再进入特征值公理库特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。分析，便知零特征值的重数恰等于 $G$ 的连通分量数。

若图没有孤立点，常用归一化 Laplacian

$$\mathcal{L}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}.$$

有孤立点时需声明约定；本页令 $D_{uu}^{-1/2}=0$，因而对应行列为零。

直觉 ​

把 $x_u$ 看作顶点 $u$ 上的温度或电势。每条边都惩罚两端数值的差，$x^{\mathsf{T}}Lx$ 汇总了全图的不协调能量。若能量为零，正权边两端必须取相同值；沿路径传播后，每个连通分量只能保持一个常数。Laplacian 因而把图的连通结构转写成矩阵的核。

$Lx$ 在顶点 $u$ 的分量是 $d_u{x}_u-\sum _v{w}_{uv}{x}_v$，也就是本点值与邻居加权值之间的差。它与连续空间中的 Laplace 算子承担相似角色：检测局部偏离平衡的程度，但图上没有坐标或微分，全部信息由边给出。

例子与边界 ​

三顶点路径 $P_3$ 的 Laplacian 为

$$L=\left(\begin{array}{ccc}1& -1& 0\\ -1& 2& -1\\ 0& -1& 1\end{array}\right),$$

其特征值是 $0,1,3$。唯一零特征方向由常向量张成，反映图连通。完全图 $K_n$ 的 Laplacian 是 $nI-J$，谱为 $0$ 一次、$n$ 重数 $n-1$；高对称性把所有与常向量正交的振动方向赋予相同能量。若图由两个互不相连的连通图组成，分别取两个分量的示性向量便得到两个线性无关的零特征向量。

这些结论不能原样套到有向图：邻接矩阵不再对称，$D-A$ 可能不是对称半正定矩阵。允许负边权时，上式会成为带符号的平方项之和，二次型可能取负值，因而失去半正定性。组合 Laplacian、归一化 Laplacian 与随机游走 Laplacian $I-D^{-1}A$ 还具有不同的特征值尺度；比较谱隙时必须先固定所用规范。

推论与应用 ​

由核的刻画可立即得到：有限无向图连通，当且仅当 $0$ 是 $L$ 的单特征值。第二小特征值因此衡量离断开还有多远，并把连通性公理库图连通性Graph connectivity任意两顶点之间都存在路时图连通。与割的瓶颈联系起来。Rayleigh 商

$$\frac{x^{\mathsf{T}}Lx}{x^{\mathsf{T}}x}$$

把寻找低能量顶点函数转为特征值问题，是谱划分和扩张估计的入口。

Laplacian 的任一主余子式还出现在矩阵树定理中，用行列式计数生成树公理库生成树Spanning tree包含原图全部顶点且自身为树的子图。；其伪逆编码电网络的有效电阻。随机游走、扩散、谱聚类和图信号平滑看似来自不同应用，实质上都在使用同一个“邻边差异能量”。

参考资料

• Daniel A. Spielman, Spectral and Algebraic Graph Theory, Yale lecture notes, Chapters 2–4.
• Fan R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997, Chapters 1–2.