Editing Laplacian matrix (section)

== Definitions for ''simple graphs''==

=== Laplacian matrix ===
Given a [[simple graph]] <math>G</math> with <math>n</math> vertices <math>v_1, \ldots, v_n</math>, its Laplacian matrix <math display="inline">L_{n \times n}</math> is 
defined element-wise as<ref name="Fan Chung">{{cite book
| last                  = Chung
| first                 = Fan
| author-link            = Fan Chung
| title                 = Spectral Graph Theory
| url                   = http://www.math.ucsd.edu/~fan/research/revised.html
| orig-year              = 1992
| year                  = 1997
| publisher             = American Mathematical Society
| isbn                  = 978-0821803158
}}</ref>
: <math>L_{i,j} := \begin{cases}
  \deg(v_i) & \mbox{if}\ i = j \\
         -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
          0 & \mbox{otherwise},
\end{cases}</math>
or equivalently by the matrix 
: <math>L = D - A, </math>

where ''D'' is the [[degree matrix]], and ''A'' is the graph's [[adjacency matrix]]. Since <math display="inline">G</math> is a simple graph, <math display="inline">A</math> only contains 1s or 0s and its diagonal elements are all 0s.

Here is a simple example of a labelled, undirected graph and its Laplacian matrix.

{|class="wikitable"
! [[Labelled graph]]
! [[Degree matrix]]
! [[Adjacency matrix]]
! Laplacian matrix
|-
| [[image:6n-graf.svg|175px]]
| <math display="inline">\left(\begin{array}{rrrrrr}
  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)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
  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)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
   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)  </math>
|}
We observe for the undirected graph that both the [[adjacency matrix]] and the Laplacian matrix are symmetric and that the row- and column-sums of the Laplacian matrix are all zeros (which directly implies that the Laplacian matrix is singular).

For [[directed graph]]s, either the [[degree (graph theory)|indegree or outdegree]] might be used, depending on the application, as in the following example:
{|class="wikitable"
!Labelled graph
! [[Adjacency matrix]]
! Out-Degree matrix
! Out-Degree Laplacian
! In-Degree matrix
! In-Degree Laplacian
|-
|[[File:3 node Directed graph.png|center|100x100px]]
| <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}
   2 &  -1 &  -1\\
   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\\
   0 &   1 &  -1\\
  -1 &   0 &   2\\
\end{array}\right)</math>
|}
In the directed graph, the [[adjacency matrix]] and Laplacian matrix are asymmetric. In its Laplacian matrix, column-sums or row-sums are zero, depending on whether the [[degree (graph theory)|indegree or outdegree]] has been used.

=== Laplacian matrix for an undirected graph via the oriented incidence matrix===
The <math display="inline">|v| \times |e|</math> oriented [[incidence matrix]] ''B'' with element ''B''<sub>''ve''</sub> for the vertex ''v''  and the edge ''e'' (connecting vertices <math display="inline">v_i</math> and <math display="inline">v_j</math>, with ''i''&nbsp;≠&nbsp;''j'') is defined by
:<math>B_{ve} = \left\{\begin{array}{rl}
   1, & \text{if } v = v_i\\
  -1, & \text{if } v = v_j\\
   0, & \text{otherwise}.
\end{array}\right.</math>
Even though the edges in this definition are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian <math display="inline">|v| \times |v|</math> matrix ''L'' defined as
:<math>L = B B^\textsf{T}</math>
where <math display="inline">B^\textsf{T}</math> is the [[transpose|matrix transpose]] of ''B''.

{|class="wikitable"
! [[Undirected graph]]
! [[Incidence matrix]]
! Laplacian matrix
|-
| [[image:Labeled_undirected_graph.svg|100px]]
| <math display="inline">\left(\begin{array}{rrrr}
   1 &  1 &  1 &  0\\
  -1 &  0 &  0 &  0\\
   0 & -1 &  0 &  1\\
   0 &  0 & -1 & -1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   3 &  -1 &  -1 & -1\\
  -1 &   1 &   0 &  0\\
  -1 &   0 &   2 & -1\\
  -1 &   0 &   -1 & 2\\
\end{array}\right)</math>
|}

An alternative product <math>B^\textsf{T}B</math> defines the so-called <math display="inline">|e| \times |e|</math> ''edge-based Laplacian,'' as opposed to the original commonly used ''vertex-based Laplacian'' matrix ''L''.

===Symmetric Laplacian for a directed graph===
The Laplacian matrix of a directed graph is by definition generally non-symmetric, while, e.g., traditional [[spectral clustering]] is primarily developed for undirected graphs with symmetric adjacency and Laplacian matrices. A trivial approach to applying techniques requiring the symmetry is to turn the original directed graph into an undirected graph and build the Laplacian matrix for the latter. 

In the matrix notation, the adjacency matrix of the undirected graph could, e.g., be defined as a [[OR gate|Boolean sum]] of the adjacency matrix <math>A</math> of the original directed graph and its [[matrix transpose]] <math>A^T</math>, where the zero and one entries of <math>A</math> are treated as logical, rather than numerical, values, as in the following example:
{|class="wikitable"
! [[Adjacency matrix]]
! Symmetrized adjacency
! Symmetric Laplacian matrix
|-
| <math display="inline">\left(\begin{array}{ccc}
  0 &  1 &  1\\
  0 &  0 &  1\\
  1 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{ccc}
  0 &  1 &  1\\
  1 &  0 &  1\\
  1 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{ccc}
   2 &  -1 &  -1\\
  -1 &   2 &  -1\\
  -1 &  -1 &   2\\
\end{array}\right)</math>
|}

=== 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>.