Normalized Laplacian matrix

Definition

Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set $V(G)$. Fix a bijective correspondence $v:\{1,2,\dots ,n\}\to V(G)$. The normalized Laplacian matrix, also called the symmetric normalized Laplacian matrix, of $G$, corresponding to this choice of bijection $v$, is a $n\times n$ square matrix denoted $\mathcal{L}$ and can be defined in the following equivalent ways:

• It is the matrix $\mathcal{L}=D^{-1/2}L{D}^{-1/2}$ where $D$ is the degree matrix and $L$ is the Laplacian matrix of $G$ (both matrices are written using the vertex ordering given by $v$).
• It is the matrix $\mathcal{L}=I-D^{-1/2}A{D}^{-1/2}$ where $I$ is the $n\times n$ identity matrix, $D$ is the degree matrix, and $A$ is the adjacency matrix of $G$ (both matrices are written using the vertex ordering given by $v$).