拉普拉斯算子

$$\begin{array}{rl}\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 _{\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{array}$$
其中$N\left(i,j\right)$表示$\left(i,j\right)$相邻的节点，例如这里是四联通（上下左右）

拉普拉斯矩阵

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

(下面针对无向图)

由于图的边可以带有权重,设$\mathbf{W}$为邻接矩阵
$$\Delta f_i=\sum _{j\in N_i}{w}_{ij}\left(f_i-f_j\right)$$
设$V$为顶点集合,$n=\left|V\right|$，$\mathbf{D}$为加权度矩阵，即$d_{ij}=\{\begin{array}{ll}{\sum }_{j=1}^n{w}_{ij},& i=j\\ 0,& otherwise\end{array}$
如果$j\notin N_i$则$w_{ij}=0$,于是
$$\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}$$
其中${\mathbf{w}}_I$表示$\mathbf{W}$的第$i$行，$\mathbf{f}=\left(\begin{array}{c}{f}_1\\ f_2\\ ⋮\\ f_n\end{array}\right)$

对于所有的点，有
$$\Delta f=\left(\begin{array}{c}\Delta f_1\\ ⋮\\ \Delta f_n\end{array}\right)=\left(\begin{array}{c}{d}_1{f}_1-{\mathbf{w}}_1\mathbf{f}\\ ⋮\\ d_n{f}_n-{\mathbf{w}}_n\mathbf{f}\end{array}\right)=\mathbf{Df}-\mathbf{Wf}=\left(\mathbf{D}-\mathbf{W}\right)\mathbf{f}$$
定义拉普拉斯矩阵为
$$\mathbf{L}=\mathbf{D}-\mathbf{W}$$

性质

性质1

$\forall \mathbf{f}\in {\mathbb{R}}^n$,有
$${\mathbf{f}}^T\mathbf{Lf}=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}{\left(f_i-f_j\right)}^2$$

证明：
$$\begin{array}{rl}{\mathbf{f}}^T\mathbf{Lf}& ={\mathbf{f}}^T\mathbf{Df}-{\mathbf{f}}^T\mathbf{Wf}\\ & =\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{array}$$

性质2

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

性质3

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

证明：
每一行加起来
${\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$
于是$\mathbf{Le}=0\mathbf{e}$

性质4

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

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

$${\mathbf{f}}^T\mathbf{Lf}=\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$
由于是连通图，最后$f_1=f_2=\cdots =f_n$（有点像并查集）
也就是说当且仅当$\mathbf{f}=t\mathbf{e}\left(t\ne 0\right)$时,${\mathbf{f}}^T\mathbf{Lf}=0$

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

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

归一化拉普拉斯矩阵

对称归一化

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

定义为
$${\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}}$$
显然这是一个对称,${\left[l_{sym}\right]}_{ij}=\{\begin{array}{ll}1& i=j\\ -\frac{w_{ij}}{\sqrt{d_{ii}{d}_{jj}}},& w_{ij}\ne 0\\ 0,& otherwise\end{array}$