下面是维基百科上的描述：

Jump to search
In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.

大意是说：在图算法领域，Laplacian matrix 有时被称为 admittance matrix, Kirchhoff matrix 或者 discrete Laplacian，它是 graph 的一种矩阵表示。Laplacian matrix 常常被用来寻找一些有用的图(graph)属性。结合基尔霍夫积分定理(Kirchhoff's theorem)，它常常被用来计算一个给定图的生成树(spanning trees) 的数目。图的 sparsest cut 可以通过 Cheeger's inequality 的拉普拉斯矩阵的第二小的特征值来近似。

---

Laplacian matrix for simple graphs

给定的一个有 n 个节点的简单图(simple graph) , Laplacian matrix L_{n\times n} 被定义为：L = D - A
这里 D 是一个 度矩阵(degree matrix), A 是一个邻接矩阵(adjacency matrix). 由于 G 是一个简单图，所以，A 中的元素仅仅可能是 0 和 1，且其对角元素全为 0. 对于 有向图(directed graphs), 将会使用 indegree 和 outdegree . 这样，L 中的每个元素是
L_{i,j} := \begin{cases} deg(v_i) &\text{if $i = j$}\\ -1 &\text{if $i \neq j$ and $v_i$ is adjacent to $v_j$}\\ 0 &\text{otherwise} \end{cases}

deg(v_i) 表示节点 i 的度。

Symmetric normalized Laplacian

拉普拉斯矩阵的对称标准化：

L^{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}

L^{sym}_{i,j} := \begin{cases} 1 &\text{if $i = j$ and $deg(v_i) \neq 0$}\\ -\frac{1}{\sqrt{deg(v_i)deg(v_j)}}&\text{if $i \neq j$ and $v_i$ is adjacent to $v_j$}\\ 0 &\text{otherwise} \end{cases}

Random walk normalized Laplacian

random-walk normalized Laplacian matrix :

L^{rw} := D^{-1}L = I - D^{-1}A
L^{sym}_{i,j} := \begin{cases} 1 &\text{if $i = j$ and $deg(v_i) \neq 0$}\\ -\frac{1}{deg(v_i)}&\text{if $i \neq j$ and $v_i$ is adjacent to $v_j$}\\ 0 &\text{otherwise} \end{cases}

更多参考 : Laplacian matrix