图的矩阵：邻接、拉普拉斯与连通性

图把对象表示为节点、关系表示为边。邻接矩阵记录谁与谁相连，度矩阵记录每个节点连接总量，图拉普拉斯 L=D-A 则把局部差异与全局连通结构连接起来。

拉普拉斯二次型

对无向图，xᵀLx 等于各边两端数值差平方的加权和。若相邻节点取值接近，能量小。这解释了图平滑、聚类和网络扩散中的作用。

常数向量在拉普拉斯零空间中。无向图零特征值的重数等于连通分量数，因此线性代数能读出图是否断开。数值计算中“等于零”需用与尺度相称的容差。

第二小特征值及特征向量反映最弱连接方向，可用于谱切分。但把连续特征向量变成离散分组还需阈值选择，结果不必是唯一最佳社区。

度差异很大时，未归一化形式可能偏向切下小度节点。不同归一化对应不同随机游走和目标，不能混用公式后只比较数值。

边如何定义、权重如何给，比求特征向量更决定结论。相关、互动和因果不是同一关系，网络模型应公开构图规则。

对少量增删边做敏感性分析，可判断聚类是否稳健。

练习：为两个由弱边连接的小团体计算拉普拉斯，观察第二特征向量并比较删除弱边后的零空间。