图拉普拉斯矩阵

图拉普拉斯矩阵是描述图结构的矩阵，是谱图理论的核心对象，在聚类、图信号处理与网络分析中有广泛应用。

定义

设无向图 $G=(V,E)$，顶点数 $n=|V|$，邻接矩阵 $A$，度矩阵 $D=\operatorname{diag}(d_1,\dots,d_n)$（$d_i$ 为顶点 $i$ 的度），则（组合）拉普拉斯矩阵为

$$L = D - A$$

分量形式

$$L_{ij} = \begin{cases} d_i & i=j \\ -1 & i \sim j \text{（相邻）}\\ 0 & \text{其他} \end{cases}$$

基本性质

• 半正定：$x^T L x = \sum_{i \sim j} (x_i - x_j)^2 \ge 0$，故特征值非负
• 最小特征值 $\lambda_1 = 0$，对应特征向量为全 1 向量（连通图）
• 特征值中 0 的重数 = 连通分量个数
• 第二小特征值 $\lambda_2$（Fiedler 值）刻画图的连通程度，用于谱聚类

复杂度注记

文中"复杂度 $O(N^3)$"针对的是用迭代法（如幂迭代、QR 算法）求拉普拉斯矩阵全部特征值/特征向量的计算成本。对稀疏图，利用稀疏结构可将复杂度降至 $O(N^{3/2})$ 或更低（Lanczos 算法）。