1. 无向加权图 $G$

图 $G$，一般用顶点集 $V$ 和顶点之间的边集 $E$ 表示，
$$G=(V,E).$$
其中， V = { v 1 , v 2 , … , v n } V=\{v_1,v_2, \dots, v_n\} V={v1​,v2​,…,vn​}， E = { ⟨ v i , v j ⟩ ∣ i , j = [ 1   . .   n ] } E=\{\langle v_i, v_j \rangle \mid i, j = [1 \text{ }.. \text{ }n] \} E={⟨vi​,vj​⟩∣i,j=[1 .. n]}，$⟨v_i,v_j⟩$ 表示顶点 $v_i$ 和顶点 $v_j$ 之间的边。

定义 $w_{ij}$ 为边 $⟨v_i,v_j⟩$ 的权重。
对于有边连接的顶点 $v_i$ 和顶点 $v_j$，$w_{ij}>0$；对于没有边连接的顶点 $v_i$ 和顶点 $v_j$，$w_{ij}=0$。
对于无向加权图，$w_{ij}=w_{ji}$，$w_{ii}=0$。

2. 邻接矩阵 $W$

将 $G$ 使用邻接矩阵来表示，得到 $W$，定义为：
$$W=\left(\begin{array}{cccc}{w}_{11}& w_{12}& \dots & w_{1n}\\ w_{21}& w_{22}& \dots & w_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ w_{n1}& w_{n2}& \dots & w_{nn}\end{array}\right)$$

3. 度矩阵 $D$

对于 $G$ 中任意一个顶点 $v_i$，$i\in [1..n]$，它的度定义为和它相连的所有边的权重之和，即
$$d_i=\sum _{j=1}^n{w}_{ij}$$

利用顶点的度，可以得到一个度矩阵 $D$，定义为：
$$D=\left(\begin{array}{ccc}{d}_1& \dots & \dots \\ \dots & d_2& \dots \\ ⋮& \ddots & ⋮\\ \dots & \dots & d_n\end{array}\right)$$
$D$ 是一个 $n\times n$ 的矩阵，并且是一个对角矩阵，只有主对角线的元素非零，其他元素全为零。主对角线上第 $i$ 个值对应 $d_i$。

4. 拉普拉斯矩阵 $L$

拉普拉斯矩阵 $L$，定义为：
$$L=D-W$$

$L$ 具有的性质：

1. $D$ 和 $W$ 是对称矩阵，因此 $L$ 也是对称矩阵；
2. 由于 $L$ 是对称矩阵，则它的所有特征值都是实数；
3. 对于任意的向量 $f$，有：
   $$f^{\text{T}}Lf=\frac{1}{2}\sum _{i,j=1}^n{w}_{ij}(f_i-f_j{)}^2$$
4. $L$ 是半正定的，且对应的 $n$ 个实数特征值都大于 0，即 $0={\lambda }_1\le {\lambda }_2\le \dots {\lambda }_n$，且最小的特征值为 0。

对于第 3 点性质，可以很容易得到。

推导：
$L$ 是一个 $n\times n$ 的矩阵，则不妨设
$f={\left[\begin{array}{cccc}{f}_1& f_2& \dots & f_n\end{array}\right]}^{\text{T}}$，则 $f^{\text{T}}=\left[\begin{array}{cccc}{f}_1& f_2& \dots & f_n\end{array}\right]$，
有
$$\Rightarrow \begin{array}{rl}{f}^{\text{T}}D& =\left[\begin{array}{cccc}{f}_1& f_2& \dots & f_n\end{array}\right]\cdot \left[\begin{array}{cccc}{d}_1& \dots & \dots & \dots \\ \dots & d_2& \dots & \dots \\ ⋮& ⋮& \ddots & ⋮\\ \dots & \dots & \dots & d_n\end{array}\right]\\ & =\left[\begin{array}{cccc}{f}_1{d}_1& f_2{d}_2& \dots & f_n{d}_n\end{array}\right]\end{array}$$

$$\Rightarrow \begin{array}{rl}{f}^{\text{T}}Df& =\left[\begin{array}{ccc}{f}_1{d}_1& f_2{d}_2& \dots f_n{d}_n\end{array}\right]\cdot \left[\begin{array}{c}{f}_1\\ f_2\\ \dots \\ f_n\end{array}\right]\\ & =\left(f_1^2{d}_1+f_2^2{d}_2+\cdots +f_n^2{d}_n\right)\\ & =\sum _{i=1}^n{f}_i^2{d}_i\end{array}$$

$$\Rightarrow \begin{array}{rl}{f}^{\text{T}}W& =\left[\begin{array}{cccc}{f}_1& f_2& \dots & f_n\end{array}\right]\cdot \left[\begin{array}{cccc}{w}_{11}& w_{12}& \dots & w_{1n}\\ w_{21}& w_{22}& \dots & w_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ w_{n1}& w_{n2}& \dots & w_{nn}\end{array}\right]\\ & ={\left[\begin{array}{c}{f}_1{w}_{11}+f_2{w}_{21}+\cdots +f_n{w}_{n1}\\ f_1{w}_{12}+f_2{w}_{22}+\cdots +f_n{w}_{n2}\\ ⋮\\ f_1{w}_{1n}+f_2{w}_{2n}+\cdots +f_n{w}_{nn}\end{array}\right]}^{\text{T}}\\ & =\left[\begin{array}{cccc}{\sum }_{i=1}^n{f}_i{w}_{i1}& {\sum }_{i=1}^n{f}_i{w}_{i2}& \cdots & {\sum }_{i=1}^n{f}_i{w}_{in}\end{array}\right]\end{array}$$

$$\Rightarrow \begin{array}{rl}{f}^{\text{T}}Wf& =\left[\begin{array}{cccc}{\sum }_{i=1}^n{f}_i{w}_{i1}& {\sum }_{i=1}^n{f}_i{w}_{i2}& \dots & {\sum }_{i=1}^n{f}_i{w}_{in}\end{array}\right]\cdot \left[\begin{array}{c}{f}_1\\ f_2\\ \dots \\ f_n\end{array}\right]\\ & =f_1\sum _{i=1}^n{f}_i{w}_{i1}+f_2\sum _{i=1}^n{f}_i{w}_{i2}+\cdots +f_n\sum _i^n{f}_i{w}_{in}\\ & =\sum _{j=1}^n{f}_j\sum _{i=1}^n{f}_i{w}_{ij}\\ & =\sum _{j=1}^n\sum _{i=1}^n{f}_i{f}_j{w}_{ij}\\ & =\sum _{i=1}^n\sum _{j=1}^n{f}_i{f}_j{w}_{ij}\end{array}$$

因此，
$$\Rightarrow \begin{array}{rl}{f}^{\text{T}}Lf& =f^{\text{T}}(D-W)f\\ & =f^{\text{T}}Df-f^{\text{T}}Wf\\ & =\sum _{i=1}^n{f}_i^2{d}_i-\sum _{j=1}^n\sum _{i=1}^n{f}_i{f}_j{w}_{ij}\\ & =\frac{1}{2}\left(\sum _i^n{f}_i^2{d}_i-2\sum _{i=1}^n\sum _{j=1}^n{f}_i{f}_j{w}_{ij}+\sum _{j=1}^n{f}_j^2{d}_j\right)\\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}(f_i-f_j{)}^2\end{array}$$

参考

1. 刘建平Pinard：谱聚类（spectral clustering）原理总结
2. 文墨：谱聚类算法(Spectral Clustering)