度矩阵D
对于图? ，用集合?和边的集合?来描述。即为?(?,?)。其中?为数据集里面所有的点(v 1 v_1v1,v 2 v_2v2,…v n v_nvn)。对于?中的任意两个点，可以有边连接，也可以没有边连接。定义权重w i j w_{ij}wij为点v i v_ivi和点v j v_jvj之间的权重。假设是无向图，所以w i j = w j i w_{ij}=w_{ji}wij=wji。
对于有边连接的两个点v i v_ivi和v j v_jvj，w i j w_{ij}wij>0,对于没有边连接的两个点v i v_ivi和v j v_jvj，w i j w_{ij}wij=0。对于图中的任意一个点v i v_ivi，它的度d i d_idi定义为和它相连的所有边的权重之和，即
d i = ∑ j = 1 n W i j d_i = \sum_{j=1}^nW_{ij}di=j=1∑nWij
利用每个点度的定义，我们可以得到一个nxn的度矩阵?,它是一个对角矩阵，只有主对角线有值，对应第i行的第i个点的度数，定义如下：
D = { d 1 ⋯ ⋯ ⋯ d 2 ⋯ ⋮ ⋮ ⋱ ⋯ ⋯ d n } (2) D= \left\{ \begin{matrix} d_1 & \cdots & \cdots \\ \cdots & d_2& \cdots \\ \vdots & \vdots & \ddots\\ \cdots & \cdots & d_n \end{matrix} \right\} \tag{2}D=⎩⎪⎪⎪⎨⎪⎪⎪⎧d1⋯⋮⋯⋯d2⋮⋯⋯⋯⋱dn⎭⎪⎪⎪⎬⎪⎪⎪⎫(2)
D是度矩阵，一个对角矩阵
邻接矩阵W
利用所有点之间的权重值，可以得到图的邻接矩阵?，它也是一个nxn的矩阵，第i行的第j个值对应权重W i j W_{ij}Wij。
W = { W 11 W 12 ⋯ ⋯ W 22 ⋯ ⋮ ⋮ ⋱ ⋯ ⋯ W n n } (2) W= \left\{ \begin{matrix} W_{11} & W_{12} & \cdots \\ \cdots & W_{22} & \cdots \\ \vdots & \vdots & \ddots\\ \cdots & \cdots & W_{nn} \end{matrix} \right\} \tag{2}W=⎩⎪⎪⎪⎨⎪⎪⎪⎧W11⋯⋮⋯W12W22⋮⋯⋯⋯⋱Wnn⎭⎪⎪⎪⎬⎪⎪⎪⎫(2)
拉普拉斯矩阵定义
? = ? − ? ?=?−?L=D−W
拉普拉斯矩阵性质：
1）拉普拉斯矩阵是对称矩阵，这可以由?和?都是对称矩阵而得。
2）由于拉普拉斯矩阵是对称矩阵，则它的所有的特征值都是实数。
3）对于任意的向量?,
f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^TLf=\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}(f_i-f_j)^2fTLf=21i,j=1∑nwij(fi−fj)2
推倒过程如下
f T L f = f T D f − f T W f = ∑ i = 1 n d i f i 2 − ∑ i , j = 1 n w i j f i f j = 1 2 ( ∑ i = 1 n d i f i 2 − 2 ∑ i , j = 1 n w i j f i f j + ∑ i = 1 n d i f j 2 ) = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^TLf = f^TDf - f^TWf = \sum_{i=1}^n d_i f_i^2 - \sum_{i,j=1}^n w_{ij} f_i f_j = \\ \frac{1}{2}( \sum_{i=1}^n d_i f_i^2 - 2\sum_{i,j=1}^n w_{ij} f_i f_j + \sum_{i=1}^n d_i f_j^2) = \frac{1}{2}\sum_{i,j=1}^{n}w_{ij}(f_i-f_j)^2fTLf=fTDf−fTWf=i=1∑ndifi2−i,j=1∑nwijfifj=21(i=1∑ndifi2−2i,j=1∑nwijfifj+i=1∑ndifj2)=21i,j=1∑nwij(fi−fj)2
4) 拉普拉斯矩阵是半正定的，且对应的n个实数特征值都大于等于0，即0=?1≤?2≤…≤??， 且最小的特征值为0，这个由性质3很容易得出。
参考：https://www.cnblogs.com/pinard/p/6221564.html