Laplacian Matrix

Definition

The Laplacian matrix is a matrix representation of a Graph. $L=D-A$ where $D$ is the Degree Matrix, and $A$ is the Adjacency Matrix of the graph.

Random Walk Normalized Laplacian Matrix

${\mathbf{L}}^{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$

Symmetrically Normalized Laplacian Matrix

${\mathbf{L}}^{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$

Examples

Laplacian Matrix for Simple Graph

Adjacency Matrix and Degree Matrix $A=\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right),D=\left(\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

Laplacian matrix $L=D-A=\left(\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right)$

Laplacian Matrix for Graph with Weighted Edges

Adjacency Matrix and Degree Matrix $A=\left(\begin{array}{cccc}0& 1& 2& 3\\ 1& 0& 0& 0\\ 2& 0& 0& 4\\ 3& 0& 4& 0\end{array}\right),D=\left(\begin{array}{cccc}6& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 6& 0\\ 0& 0& 0& 7\end{array}\right),$

Laplacian matrix $L=D-A=\left(\begin{array}{cccc}6& -1& -2& -3\\ -1& 1& 0& 0\\ -2& 0& 6& -4\\ -3& 0& -4& 7\end{array}\right)$

Facts

The number of zero-eigenvalues of the Laplacian matrix equals the number of connected clusters in the graph.

Analogousness to the Laplace-Beltrami Operator

The Laplacian matrix on a graph, $\mathbf{L}$ can be ragarded as a discrete approximation to the Laplace-Beltrami Operator on a manifold.

The quadratic form of the Laplacian Matrix can be seen as a discretization of squared gradient on manifold.

${\mathbf{z}}^{⊺}\mathbf{Lz}=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}({\mathbf{z}}_i-{\mathbf{z}}_j{)}^2=\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n\left(\frac{{\mathbf{z}}_i-{\mathbf{z}}_j}{d_{ij}}\right)\approx {\int }_{\mathcal{M}}||\nabla f(x)|{|}^2={\int }_{\mathcal{M}}\mathcal{L}(f)\cdot f$ where $d_{ij}^2:=\frac{1}{a_{ij}}$ is a distance between two points ${\mathbf{x}}_i$ and ${\mathbf{x}}_j$ defined by the Adjacency Matrix.