Editing Laplacian matrix (section)

==== Random walk normalized Laplacian ====

The '''random walk normalized Laplacian''' is defined as
: <math>L^\text{rw} := D^+ L = I - D^+ A</math>

where ''D'' is the degree matrix. Since the degree matrix ''D'' is diagonal, its inverse <math display="inline">D^+</math> is simply defined as a diagonal matrix, having diagonal entries which are the reciprocals of the corresponding diagonal entries of ''D''. For the isolated vertices (those with degree 0), a common choice is to set the corresponding element <math display="inline">L^\text{rw}_{i,i}</math> to 0. The matrix 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>

The name of the random-walk normalized Laplacian comes from the fact that this matrix is <math display="inline">L^\text{rw} = I - P</math>, where <math display="inline">P = D^+A</math> is simply the transition matrix of a random walker on the graph, assuming non-negative weights. For example, let <math display="inline"> e_i </math> denote the i-th [[standard basis]] vector. Then <math display="inline">x = e_i P </math> is a [[probability vector]] representing the distribution of a random walker's locations after taking a single step from vertex <math display="inline">i</math>; i.e., <math display="inline">x_j = \mathbb{P}\left(v_i \to v_j\right)</math>. More generally, if the vector <math display="inline"> x </math> is a probability distribution of the location of a random walker on the vertices of the graph, then <math display="inline">x' = x P^t</math> is the probability distribution of the walker after <math display="inline">t</math> steps.

The random walk normalized Laplacian can also be called the left normalized Laplacian <math>L^\text{rw} := D^+L</math> since the normalization is performed by multiplying the Laplacian by the normalization matrix <math>D^+</math> on the left. It has each row summing to zero since <math>P = D^+A</math> is [[Stochastic matrix|right stochastic]], assuming all the weights are non-negative.

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 &  0\\
  0 &  0 &  2\\
  1 &  0 &  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\\
   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 &   0\\
   0 &   1 &  -1\\
  -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>.