高等数学 / 系统课时
用图拉普拉斯分析网络结构
用图拉普拉斯分析网络结构
图的边描述对象之间的连接,但仅看邻接矩阵并不容易直接判断整体连通结构。图拉普拉斯矩阵把节点度数与邻接关系组合起来,其最小特征值附近的信息能够直接揭示连通分量,是谱图方法中最重要的线性代数入口之一。
学习目标
- 从邻接矩阵和度矩阵构造图拉普拉斯矩阵
- 解释图拉普拉斯零特征值及其对应特征向量的含义
- 根据零特征值的多重度判断无向图的连通分量数量
从邻接矩阵得到图拉普拉斯
对一个无向图,邻接矩阵 用 表示节点 与节点 之间存在边。度矩阵 是对角矩阵,第 个对角元素等于节点 的度数。
组合二者即可得到未归一化图拉普拉斯矩阵:
因此 的对角元素记录每个节点连接了多少条边,非对角位置在相邻节点之间为负值。每一行元素之和都等于 0,所以全 1 向量一定满足 ,这已经说明 0 必然是图拉普拉斯的一个特征值。

零特征值为什么表示连通性
如果图只有一个连通分量,所有节点可以通过边彼此到达,那么图拉普拉斯的零特征空间只有一个独立方向,通常由常量向量表示,因此特征值 0 的多重度为 1。
如果图分成多个互不相连的连通分量,每个分量都可以构造一个指示向量:属于该分量的节点取 1,其余节点取 0。由于分量之间没有边,这些向量分别都满足 ,并且彼此线性无关。
因此,对无向图有一个非常实用的结论:图拉普拉斯矩阵中特征值 0 的多重度,等于图的连通分量数量。 一个零特征值表示图连通,两个零特征值表示有两个连通分量,以此类推。
用代码计算连通分量数量
下面构造一个五节点无向图。节点 0、1、2 构成一个三角形,节点 3、4 构成第二个分量,因此预期会得到两个零特征值。
import numpy as np
A = np.array([
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0],
], dtype=float)
# 度矩阵由邻接矩阵每一行的连接数构成。
D = np.diag(A.sum(axis=1))
L = D - A
eigenvalues = np.linalg.eigvalsh(L)
eigenvalues[np.isclose(eigenvalues, 0.0, atol=1e-9)] = 0.0
zero_count = np.sum(np.isclose(eigenvalues, 0.0, atol=1e-9))
print(L.astype(int))
print("eigenvalues:", np.round(eigenvalues, 6).tolist())
print("zero multiplicity:", int(zero_count))预期输出
[[ 2 -1 -1 0 0]
[-1 2 -1 0 0]
[-1 -1 2 0 0]
[ 0 0 0 1 -1]
[ 0 0 0 -1 1]]
eigenvalues: [0.0, 0.0, 2.0, 3.0, 3.0]
zero multiplicity: 2矩阵中左上角的 块和右下角的 块之间没有非零连接项,这正对应两个独立子图;谱中两个零特征值给出了同样的结论。
谱信息还能说明什么
当图连通时,第二小的拉普拉斯特征值常被称为代数连通度。它越接近 0,通常意味着图虽然仍然连通,但存在较弱的连接瓶颈;相应特征向量还能帮助把网络切分为内部连接较强、彼此连接较弱的节点组。
这也是谱聚类、网络划分和图信号处理能够使用特征分解的原因:图拉普拉斯把离散的边关系转成了对称矩阵,使连通性、分区与变化平滑程度都能通过矩阵的特征值和特征向量研究。