图拉普拉斯矩阵

图拉普拉斯矩阵把网络的结构变成一个矩阵，其谱能读出网络有多连通，以及它倾向于如何被切开。它是微积分中拉普拉斯算子的离散表亲，衡量一个节点上的值与其邻居相差多少。

定义为 L = D - A，其中 A 是邻接矩阵，D 是对角度数矩阵（D_ii 是节点 i 的边数）。L 对称且半正定，并有一个优美的二次型恒等式：x^T L x = 对所有边 (i,j) 求和 (x_i - x_j)^2。故 L 衡量一种标号在所有边上的总平方差异。

它的特征值 0 = lambda_1 <= lambda_2 <= ... <= lambda_n 意义深远。最小特征值恒为 0，对应全一特征向量，而零特征值的个数等于连通分量的个数。第二个特征值 lambda_2（代数连通度）恰在图连通时为正。

为何重要：拉普拉斯矩阵驱动谱聚类、图绘制、网格平滑，以及网络上扩散与随机游走的分析。一个警示：朴素的 L 有度数偏置，故做聚类时常用归一化版本（对称型或随机游走型），以防高度数的枢纽节点主导。