Editing Laplacian matrix (section)

=== Laplacian matrix normalization ===
A vertex with a large degree, also called a ''heavy node'', results in a large diagonal entry in the Laplacian matrix dominating the matrix properties. Normalization is aimed to make the influence of such vertices more equal to that of other vertices, by dividing the entries of the Laplacian matrix by the vertex degrees. To avoid division by zero, isolated vertices with zero degrees are excluded from the process of the normalization. 

==== Symmetrically normalized Laplacian ====

The symmetrically normalized Laplacian matrix is defined as:<ref name="Fan Chung" />

: <math>L^\text{sym} := (D^+)^{1/2} L (D^+)^{1/2} = I - (D^+)^{1/2} A (D^+)^{1/2},</math>
where <math>D^+</math> is the [[Moore–Penrose inverse]] of the degree matrix.

The elements of <math display="inline">L^\text{sym}</math> are thus given by

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

The symmetrically normalized Laplacian matrix is symmetric if and only if the adjacency matrix is symmetric. 
{|class="wikitable"
! [[Adjacency matrix]]
! Degree matrix
! Normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  0\\
  1 &  0 &  1\\
  0 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  2 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -\sqrt{1/2} &  0\\
   -\sqrt{1/2} &   1 &  -\sqrt{1/2}\\
  0&   -\sqrt{1/2} &   1\\
\end{array}\right)</math>
|}

For a non-symmetric adjacency matrix of a directed graph, either of [[degree (graph theory)|indegree and outdegree]] can be used for normalization:
{|class="wikitable"
! [[Adjacency matrix]]
! Out-Degree matrix
! Out-Degree normalized Laplacian
! In-Degree matrix
! In-Degree normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  1\\
  0 &  0 &  1\\
  1 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  2 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -\sqrt{1/2} &  -\sqrt{1/2}\\
   0 &   1 &  -1\\
  -\sqrt{1/2}&   0 &   1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  2\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1 &  -\sqrt{1/2}\\
   0 &   1 &  -\sqrt{1/2}\\
  -\sqrt{1/2}&   0 &   1\\
\end{array}\right)</math>
|}

==== Left (random-walk) and right normalized Laplacians ====

The left (random-walk) normalized Laplacian matrix is defined as:
: <math>L^\text{rw} := D^+L = I - D^+A,</math>
where <math>D^+</math> is the [[Moore–Penrose inverse]].
The elements of <math display="inline">L^\text{rw}</math> are given by
:<math>L^\text{rw}_{i,j} := \begin{cases}
                     1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                     0 & \mbox{otherwise}.
\end{cases}</math>

Similarly, the right normalized Laplacian matrix is defined as 
: <math>L D^+ = I - A D^+</math>.

The left or right normalized Laplacian matrix is not symmetric if the adjacency matrix is symmetric, except for the trivial case of all isolated vertices. For example, 
{|class="wikitable"
! [[Adjacency matrix]]
! Degree matrix
! Left normalized Laplacian
! Right normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  0\\
  1 &  0 &  1\\
  0 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  2 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1 &  0\\
   -1/2 &   1 &  -1/2\\
  0&   -1 &   1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1/2 &  0\\
   -1 &   1 &  -1\\
  0&   -1/2 &   1\\
\end{array}\right)</math>
|}
The example also demonstrates that if <math>G</math> has no isolated vertices, then <math>D^+A</math> [[Stochastic matrix|right stochastic]] and hence is the matrix of a [[random walk]], so that the left normalized Laplacian <math>L^\text{rw} := D^+L = I - D^+A</math> has each row summing to zero. Thus we sometimes alternatively call <math>L^\text{rw}</math> the [[random walk|random-walk]] normalized Laplacian. In the less uncommonly used right normalized Laplacian <math>L D^+ = I - A D^+</math> each column sums to zero since <math>A D^+</math> is [[Stochastic matrix|left stochastic]]. 

For a non-symmetric adjacency matrix of a directed graph, one also needs to choose [[degree (graph theory)|indegree or outdegree]] for normalization:
{|class="wikitable"
! [[Adjacency matrix]]
! Out-Degree matrix
! Out-Degree left normalized Laplacian
! In-Degree matrix
! In-Degree right normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  1\\
  0 &  0 &  1\\
  1 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  2 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1/2 &  -1/2\\
   0 &   1 &  -1\\
  -1 &   0 &   1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  2\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1 &  -1/2\\
   0 &   1 &  -1/2\\
  -1 &   0 &   1\\
\end{array}\right)</math>
|}
The left out-degree normalized Laplacian with row-sums all 0 relates to [[Stochastic matrix|right stochastic]] <math>D_{\text{out}}^+A</math> , while the right in-degree normalized Laplacian  with column-sums all 0 contains [[Stochastic matrix|left stochastic]]  <math>AD_{\text{in}}^+</math>.