当前位置：首页 > news >正文

拉普拉斯矩阵

news 2025/7/12 10:13:22

拉普拉斯算子

$Δf=f(xi+1,yj)+f(xi−1,yj)+f(xi,yj+1)+f(xi,yj−1)−4f(xi,yj)=∑(k,l)∈N(i,j)(f(xk,yl)−f(xi,yj))\begin{aligned} \Delta f &= f\left(x_{i+1}, y_j\right) + f\left(x_{i-1},y_j\right) + f\left(x_i,y_{j+1}\right)+f\left(x_i,y_{j-1}\right) - 4f\left(x_i,y_j\right)\\ &=\sum\limits_{\left(k,l\right) \in N\left(i,j\right)}\left(f\left(x_k,y_l\right) - f\left(x_i,y_j\right)\right) \end{aligned}$
其中 $N(i,j)N\left(i,j\right)$ 表示 $(i,j)\left(i,j\right)$ 相邻的节点，例如这里是四联通（上下左右）

拉普拉斯矩阵

前面的拉普拉斯算子是上下左右，而图的顶点的连接关系可以是任意的，下面将拉普拉斯算子推广到图。
如果将图的顶点处的值看作是函数值，则在顶点 $i$ 的拉普拉斯算子为
$Δfi=∑j∈Ni(fi−fj)\Delta f_i = \sum_{j \in N_i}\left(f_i-f_j\right)$
这里的拉普拉斯算子和上面的拉普拉斯算子查了个负号

(下面针对无向图)

由于图的边可以带有权重,设 $W\mathbf{W}$ 为邻接矩阵
$Δfi=∑j∈Niwij(fi−fj)\Delta f_i = \sum_{j \in N_i}w_{ij}\left(f_i-f_j\right)$
设 $V$ 为顶点集合, $\left|V\right|$ ， $D\mathbf{D}$ 为加权度矩阵，即 $dij={∑j=1nwij,i=j0,otherwised_{ij} = \begin{cases} \sum_{j=1}^{n}w_{ij},& i = j\\ 0,&otherwise\\ \end{cases}$
如果 $j∉Nij\notin N_i$ 则 $w_{ij} = 0$ ,于是
$Δfi=∑j∈Vwij(fi−fj)=∑j∈Vwijfi−∑j∈Vwijfj=diifi−wif\Delta f_i = \sum_{j \in V}w_{ij}\left(f_i-f_j\right) = \sum_{j \in V}w_{ij}f_i - \sum_{j \in V}w_{ij}f_j = d_{ii} f_i - \mathbf{w}_i\mathbf{f}$
其中 $wI\mathbf{w}_I$ 表示 $W\mathbf{W}$ 的第 $i$ 行， $f=(f1f2⋮fn)\mathbf{f} = \begin{pmatrix} f_1\\ f_2\\ \vdots\\ f_n\\ \end{pmatrix}$

对于所有的点，有
$Δf=(Δf1⋮Δfn)=(d1f1−w1f⋮dnfn−wnf)=Df−Wf=(D−W)f\Delta f = \begin{pmatrix} \Delta f_1\\ \vdots \\ \Delta f_n \end{pmatrix} = \begin{pmatrix} d_1 f_1 - \mathbf{w}_1 \mathbf{f}\\ \vdots \\ d_n f_n - \mathbf{w}_n \mathbf{f}\\ \end{pmatrix}=\mathbf{D}\mathbf{f} - \mathbf{W}\mathbf{f} = \left(\mathbf{D} - \mathbf{W} \right) \mathbf{f}$
定义拉普拉斯矩阵为
$L=D−W\mathbf{L} = \mathbf{D} - \mathbf{W}$

性质

性质1

$∀f∈Rn\forall \mathbf{f}\in\mathbb{R}^n$ ,有
$fTLf=12∑i=1n∑j=1nwij(fi−fj)2\mathbf{f}^T\mathbf{L}\mathbf{f}=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}\left(f_i-f_j\right)^2$

证明：
$fTLf=fTDf−fTWf=∑i=1ndiifi2−∑i=1n∑j=1nfifjwij=12(2∑i=1ndiifi2−2∑i=1n∑j=1nfifjwij)=12(∑i=1ndiifi2−2∑i=1n∑j=1nfifjwij+∑j=1ndjjfj2)=12(∑i=1n∑j=1nwijfi2−2∑i=1n∑j=1nfifjwij+∑j=1n∑i=1nwjifj2)=12(∑i=1n∑j=1nwijfi2−2∑i=1n∑j=1nfifjwij+∑i=1n∑j=1nwjifj2)=12(∑i=1n∑j=1nwijfi2−2∑i=1n∑j=1nfifjwij+∑i=1n∑j=1nwijfj2)=12∑i=1n∑j=1nwij(fi−fj)2\begin{aligned} \mathbf{f}^T\mathbf{L}\mathbf{f} &= \mathbf{f}^T\mathbf{D}\mathbf{f} - \mathbf{f}^T\mathbf{W} \mathbf{f}\\ &=\sum_{i=1}^{n}d_{ii} f_i^2 - \sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij}\\ &=\frac{1}{2}\left(2\sum_{i=1}^{n}d_{ii} f_i^2 - 2\sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij}\right)\\ &=\frac{1}{2}\left(\sum_{i=1}^{n}d_{ii} f_i^2 - 2\sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij} + \sum_{j=1}^{n}d_{jj} f_j^2\right)\\ &=\frac{1}{2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij} f_i^2 - 2\sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij} + \sum_{j=1}^{n}\sum_{i=1}^{n}w_{ji} f_j^2\right)\\ &=\frac{1}{2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij} f_i^2 - 2\sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij} + \sum_{i=1}^{n}\sum_{j=1}^{n}w_{ji} f_j^2\right)\\ &=\frac{1}{2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij} f_i^2 - 2\sum_{i=1}^{n}\sum_{j=1}^{n}f_i f_j w_{ij} + \sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij} f_j^2\right)\\ &=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}\left(f_i-f_j\right)^2 \end{aligned}$

性质2

$L⪰0\mathbf{L}\succeq 0$
由性质1，显然

性质3

最小特征值为0，对应的特征向量为 $e\mathbf{e}$ ,即全1的向量

证明：
每一行加起来
$∑j=1nlij=∑j=1n(dij−wij)=dii−∑j=1nwij=0\sum_{j=1}^{n} l_{ij} = \sum_{j=1}^{n}\left(d_{ij} - w_{ij}\right) = d_{ii}-\sum_{j=1}^{n}w_{ij} = 0$
于是 $Le=0e\mathbf{L}\mathbf{e} = 0\mathbf{e}$

性质4

设 $G\mathbf{G}$ 是一个非负权重的无向图，则其拉普拉斯矩阵 $L\mathbf{L}$ 的特征值0的重数 $k$ 等于图的连通分量的个数

证明：
当 $k = 1$ 时，即连通图

$fTLf=12∑i=1n∑j=1nwij(fi−fj)2=12∑(i,j)wij(fi−fj)2=0\mathbf{f}^T\mathbf{L}\mathbf{f}=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}\left(f_i-f_j\right)^2=\frac{1}{2}\sum_{\left(i,j\right)}w_{ij}\left(f_i-f_j\right)^2=0$
对于 $w_{ij}>0$ ,有 $f_i = f_j$
由于是连通图，最后 $f1=f2=⋯=fnf_1 = f_2 = \cdots = f_n$ （有点像并查集）
也就是说当且仅当 $f=te(t≠0)\mathbf{f} = t\mathbf{e}\left(t\neq 0\right)$ 时, $fTLf=0\mathbf{f}^T\mathbf{L}\mathbf{f} = 0$

因为特征值 $0$ 对应的特征向量只有 $tet\mathbf{e}$ ，所以重数为1

假设 $k - 1$ 的时候成立
$k$ 时
不妨假设顶点按照其所属的联通分量排序
则对应的拉普拉斯矩阵是一个分块矩阵，
$L=(L1L2⋱Lk)\mathbf{L} = \begin{pmatrix} \mathbf{L}_1&&& \\ &\mathbf{L}_2&&\\ &&\ddots&\\ &&&\mathbf{L}_k \end{pmatrix}$
令 $f=(0⋮01⋮10⋮0)\mathbf{f} = \begin{pmatrix} 0\\ \vdots\\ 0\\ 1\\ \vdots\\ 1\\ 0\\ \vdots\\ 0\\ \end{pmatrix}$ ，每一个分块矩阵对应的分量为1，剩下的为0
有 $fTLf=0\mathbf{f}^T\mathbf{L}\mathbf{f} = 0$
这样的 $f\mathbf{f}$ 有 $k$ 个

归一化拉普拉斯矩阵

对称归一化

盲猜针对无向图，并且没有孤立点和自环，这样才能保证 $dii≠0,wii=0,wij=wjid_{ii} \neq 0,w_{ii} = 0,w_{ij} = w_{ji}$

定义为
$Lsym=D−12LD−12=I−D−12WD−12\mathbf{L}_{sym} = \mathbf{D}^{-\frac{1}{2}}\mathbf{L}\mathbf{D}^{-\frac{1}{2}} = \mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{W}\mathbf{D}^{-\frac{1}{2}}$
显然这是一个对称, $[lsym]ij={1i=j−wijdiidjj,wij≠00,otherwise\left[l_{sym}\right]_{ij} = \begin{cases} 1&i = j\\ -\frac{w_{ij}}{\sqrt{d_{ii}d_{jj}}},&w_{ij}\neq 0\\ 0,&otherwise\\ \end{cases}$