高等数学 / 系统课时

用图拉普拉斯分析网络结构

用图拉普拉斯分析网络结构

图的边描述对象之间的连接,但仅看邻接矩阵并不容易直接判断整体连通结构。图拉普拉斯矩阵把节点度数与邻接关系组合起来,其最小特征值附近的信息能够直接揭示连通分量,是谱图方法中最重要的线性代数入口之一。

学习目标

  • 从邻接矩阵和度矩阵构造图拉普拉斯矩阵
  • 解释图拉普拉斯零特征值及其对应特征向量的含义
  • 根据零特征值的多重度判断无向图的连通分量数量

从邻接矩阵得到图拉普拉斯

对一个无向图,邻接矩阵 AA 用 Aij=1A_{ij}=1 表示节点 ii 与节点 jj 之间存在边。度矩阵 DD 是对角矩阵,第 ii 个对角元素等于节点 ii 的度数。

组合二者即可得到未归一化图拉普拉斯矩阵:

L=D−AL=D-A

因此 LL 的对角元素记录每个节点连接了多少条边,非对角位置在相邻节点之间为负值。每一行元素之和都等于 0,所以全 1 向量一定满足 L1=0L\mathbf{1}=0,这已经说明 0 必然是图拉普拉斯的一个特征值。

图结构到拉普拉斯矩阵再到谱的关系

零特征值为什么表示连通性

如果图只有一个连通分量,所有节点可以通过边彼此到达,那么图拉普拉斯的零特征空间只有一个独立方向,通常由常量向量表示,因此特征值 0 的多重度为 1。

如果图分成多个互不相连的连通分量,每个分量都可以构造一个指示向量:属于该分量的节点取 1,其余节点取 0。由于分量之间没有边,这些向量分别都满足 Lv=0Lv=0,并且彼此线性无关。

因此,对无向图有一个非常实用的结论:图拉普拉斯矩阵中特征值 0 的多重度,等于图的连通分量数量。 一个零特征值表示图连通,两个零特征值表示有两个连通分量,以此类推。

用代码计算连通分量数量

下面构造一个五节点无向图。节点 0、1、2 构成一个三角形,节点 3、4 构成第二个分量,因此预期会得到两个零特征值。

python
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))

预期输出

text
[[ 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

矩阵中左上角的 3×33\times3 块和右下角的 2×22\times2 块之间没有非零连接项,这正对应两个独立子图;谱中两个零特征值给出了同样的结论。

谱信息还能说明什么

当图连通时,第二小的拉普拉斯特征值常被称为代数连通度。它越接近 0,通常意味着图虽然仍然连通,但存在较弱的连接瓶颈;相应特征向量还能帮助把网络切分为内部连接较强、彼此连接较弱的节点组。

这也是谱聚类、网络划分和图信号处理能够使用特征分解的原因:图拉普拉斯把离散的边关系转成了对称矩阵,使连通性、分区与变化平滑程度都能通过矩阵的特征值和特征向量研究。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用图拉普拉斯分析网络结构

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通