Laplacian matrix

Given a simple graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices ${\displaystyle v_{1},\ldots ,v_{n}}$, its Laplacian matrix ${\textstyle L_{n\times n}}$ is defined element-wise as[1]

${\displaystyle 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}}}$

or equivalently by the matrix

${\displaystyle L=D-A,}$

where D is the degree matrix and A is the adjacency matrix of the graph. Since ${\textstyle G}$ is a simple graph, ${\textstyle A}$ 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.

Labelled graph	Degree matrix	Adjacency matrix	Laplacian matrix
	${\textstyle \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)}$	${\textstyle \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)}$	${\textstyle \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)}$

We observe for the undirected graph that both the adjacency matrix and the Laplacian matrix are symmetric, and that row- and column-sums of the Laplacian matrix are all zeros.

For directed graphs, either the indegree or outdegree might be used, depending on the application, as in the following example:

Labelled graph	Adjacency matrix	Out-Degree matrix	Out-Degree Laplacian	In-Degree matrix	In-Degree Laplacian
	${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

In the directed graph, both the adjacency matrix and the Laplacian matrix are asymmetric. In its Laplacian matrix, column-sums or row-sums are zero, depending on whether the indegree or outdegree has been used.

The ${\textstyle |v|\times |e|}$ incidence matrix B with element B_ve for the vertex v and the edge e (connecting vertices ${\textstyle v_{i}}$ and ${\textstyle v_{j}}$, with i > j) is defined by

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

Even though the edges in this definition are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian ${\textstyle |v|\times |v|}$ matrix L defined as

${\displaystyle L=BB^{\textsf {T}}}$

where ${\textstyle B^{\textsf {T}}}$ is the matrix transpose of B.

Undirected graph	Incidence matrix	Laplacian matrix
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}3&-1&-1&-1\\-1&1&0&0\\-1&0&2&-1\\-1&0&-1&2\\\end{array}}\right)}$

An alternative product ${\displaystyle B^{\textsf {T}}B}$ defines the so-called ${\textstyle |e|\times |e|}$ edge-based Laplacian, as opposed to the original commonly used vertex-based Laplacian matrix L.

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 apply 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 Boolean sum of the adjacency matrix ${\displaystyle A}$ of the original directed graph and its matrix transpose ${\displaystyle A^{T}}$, where the zero and one entries of ${\displaystyle A}$ are treated as logical, rather than numerical, values, as in the following example:

Adjacency matrix	Symmetrized adjacency	Symmetric Laplacian matrix
${\textstyle \left({\begin{array}{ccc}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{ccc}2&-1&-1\\-1&2&-1\\-1&-1&2\\\end{array}}\right)}$

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.

The symmetrically normalized Laplacian matrix is defined as:[1]

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

where ${\displaystyle D^{+}}$ is the Moore–Penrose inverse.

The elements of ${\textstyle L^{\text{sym}}}$ are thus given by

${\displaystyle L_{i,j}^{\text{sym}}:={\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}}}$

The symmetrically normalized Laplacian matrix is symmetric if and only if the adjacency matrix is symmetric.

Adjacency matrix	Degree matrix	Normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&0\\-{\sqrt {1/2}}&1&-{\sqrt {1/2}}\\0&-{\sqrt {1/2}}&1\\\end{array}}\right)}$

For a non-symmetric adjacency matrix of a directed graph, either of indegree and outdegree can be used for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree normalized Laplacian	In-Degree matrix	In-Degree normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-{\sqrt {1/2}}&-{\sqrt {1/2}}\\0&1&-1\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-{\sqrt {1/2}}\\0&1&-{\sqrt {1/2}}\\-{\sqrt {1/2}}&0&1\\\end{array}}\right)}$

The left (random-walk) normalized Laplacian matrix is defined as:

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A,}$

where ${\displaystyle D^{+}}$ is the Moore–Penrose inverse. The elements of ${\textstyle L^{\text{rw}}}$ are given by

${\displaystyle L_{i,j}^{\text{rw}}:={\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}}}$

Similarly, the right normalized Laplacian matrix is defined as

${\displaystyle LD^{+}=I-AD^{+}}$.

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,

Adjacency matrix	Degree matrix	Left normalized Laplacian	Right normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\-1/2&1&-1/2\\0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-1&1&-1\\0&-1/2&1\\\end{array}}\right)}$

The example also demonstrates that if ${\displaystyle G}$ has no isolated vertices, then ${\displaystyle D^{+}A}$ right stochastic and hence is the matrix of a random walk, so that the left normalized Laplacian ${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$ has each row summing to zero. Thus we sometimes alternatively call ${\displaystyle L^{\text{rw}}}$ the random-walk normalized Laplacian. In the less uncommonly used right normalized Laplacian ${\displaystyle LD^{+}=I-AD^{+}}$ each column sums to zero since ${\displaystyle AD^{+}}$ is left stochastic.

For a non-symmetric adjacency matrix of a directed graph, one also needs to choose indegree or outdegree for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree left normalized Laplacian	In-Degree matrix	In-Degree right normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&-1/2\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1/2\\0&1&-1/2\\-1&0&1\\\end{array}}\right)}$

The left out-degree normalized Laplacian with row-sums all 0 relates to right stochastic ${\displaystyle D_{\text{out}}^{+}A}$ , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic ${\displaystyle AD_{\text{in}}^{+}}$.

The Laplacian matrix is defined by

${\displaystyle L=D-A,}$

where D is the degree matrix and A is the adjacency matrix of the graph.

For directed graphs, either the indegree or outdegree might be used, depending on the application, as in the following example:

Adjacency matrix	In-Degree matrix	In-Degree Laplacian	Out-Degree matrix	Out-Degree Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&2\\3&0&5\\6&7&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&0&0\\0&8&0\\0&0&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}9&-1&-2\\-3&8&-5\\-6&-7&7\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&0&0\\0&8&0\\0&0&13\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-3&8&-5\\-6&-7&13\\\end{array}}\right)}$

Graph self-loops, manifesting themselves by non-zero entries on the main diagonal of the adjacency matrix, are allowed but do not affect the graph Laplacian values.

A 2-dimensional spring system.

For graphs with weighted edges one can define a weighted incidence matrix B and use it to construct the corresponding symmetric Laplacian as ${\displaystyle L=BB^{\textsf {T}}}$. An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using the incidence matrix as for regular graphs and introduce a matrix just holding the values of the weights. A spring system is an example of this model used in mechanics to describe a system of springs of given stiffnesses and unit length, where the values of the stiffnesses play the role of the weights of the graph edges.

We thus reuse the definition of the weightless ${\textstyle |v|\times |e|}$ incidence matrix B with element B_ve for the vertex v and the edge e (connecting vertexes ${\textstyle v_{i}}$ and ${\textstyle v_{j}}$, with i > j) defined by

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

We now also define a diagonal ${\textstyle |e|\times |e|}$ matrix W containing the edge weights. Even though the edges in the definition of B are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian ${\textstyle |v|\times |v|}$ matrix L defined as

${\displaystyle L=BWB^{\textsf {T}}}$

where ${\textstyle B^{\textsf {T}}}$ is the matrix transpose of B.

The construction is illustrated in the following example, where every edge ${\textstyle e_{i}}$ is assigned the weight value i, with ${\textstyle i=1,2,3,4.}$

Undirected graph	Incidence matrix	Edge weights	Laplacian matrix
	${\textstyle \left({\begin{array}{rrrr}1&1&1&0\\-1&0&0&0\\0&-1&0&1\\0&0&-1&-1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}6&-1&-2&-3\\-1&1&0&0\\-2&0&6&-4\\-3&0&-4&7\\\end{array}}\right)}$

Just like for simple graphs, the Laplacian matrix of a directed weighted graph is by definition generally non-symmetric. The symmetry can be enforced by turning the original directed graph into an undirected graph first before constructing the Laplacian. The adjacency matrix of the undirected graph could, e.g., be defined as a sum of the adjacency matrix ${\displaystyle A}$ of the original directed graph and its matrix transpose ${\displaystyle A^{T}}$ as in the following example:

Adjacency matrix	Symmetrized adjacency matrix	Symmetric Laplacian matrix
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}0&1&2\\1&0&1\\2&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}3&-1&-2\\-1&2&-1\\-2&-1&3\\\end{array}}\right)}$

where the zero and one entries of ${\displaystyle A}$ are treated as numerical, rather than logical as for simple graphs, values, explaining the difference in the results - for simple graphs, the symmetrized graph still needs to be simple with its symmetrized adjacency matrix having only logical, not numerical values, e.g., the logical sum is 1 v 1 = 1, while the numeric sum is 1 + 1 = 2.

Alternatively, the symmetric Laplacian matrix can be calculated from the two Laplacians using the indegree and outdegree, as in the following example:

Adjacency matrix	Out-Degree matrix	Out-Degree Laplacian	In-Degree matrix	In-Degree Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

The sum of the out-degree Laplacian transposed and the in-degree Laplacian equals to the symmetric Laplacian matrix.

The goal of normalization is, like for simple graphs, to make the diagonal entries of the Laplacian matrix to be all unit, also scaling off-diagonal entries correspondingly. In a weighted graph, a vertex may have a large degree because of a small number of connected edges but with large weights just as well as due to a large number of connected edges with unit weights.

Graph self-loops, i.e., non-zero entries on the main diagonal of the adjacency matrix, do not affect the graph Laplacian values, but may need to be counted for calculation of the normalization factors.

The symmetrically normalized Laplacian is defined as

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

where L is the unnormalized Laplacian, A is the adjacency matrix, D is the degree matrix, and ${\displaystyle D^{+}}$ is the Moore–Penrose inverse. Since the degree matrix D is diagonal, its reciprocal square root ${\textstyle (D^{+})^{1/2}}$ is just the diagonal matrix whose diagonal entries are the reciprocals of the square roots of the diagonal entries of D. If all the edge weights are nonnegative then all the degree values are automatically also nonnegative and so every degree value has a unique positive square root. To avoid the division by zero, vertices with zero degrees are excluded from the process of the normalization, as in the following example:

Adjacency matrix	In-Degree matrix	In-Degree normalized Laplacian	Out-Degree matrix	Out-Degree normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&0\\4&0&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&4&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}4&0&0\\0&1&0\\0&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1/2&0\\-2&1&0\\0&0&0\\\end{array}}\right)}$

The symmetrically normalized Laplacian is a symmetric matrix if and only if the adjacency matrix A is symmetric and the diagonal entries of D are nonnegative, in which case we can use the term the symmetric normalized Laplacian.

The symmetric normalized Laplacian matrix can be also written as

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=(D^{+})^{1/2}BWB^{\textsf {T}}(D^{+})^{1/2}=SS^{T}}$

using the weightless ${\textstyle |v|\times |e|}$ incidence matrix B and the diagonal ${\textstyle |e|\times |e|}$ matrix W containing the edge weights and defining the new ${\textstyle |v|\times |e|}$ weighted incidence matrix ${\textstyle S=(D^{+})^{1/2}BW^{{1}/{2}}}$ whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge e = {u, v} has an entry ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ in the row corresponding to u, an entry ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$ in the row corresponding to v, and has 0 entries elsewhere.

The random walk normalized Laplacian is defined as

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$

where D is the degree matrix. Since the degree matrix D is diagonal, its inverse ${\textstyle D^{+}}$ 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 ${\textstyle L_{i,i}^{\text{rw}}}$ to 0. The matrix elements of ${\textstyle L^{\text{rw}}}$ are given by

${\displaystyle L_{i,j}^{\text{rw}}:={\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}}}$

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

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

In the less uncommonly used right normalized Laplacian ${\displaystyle LD^{+}=I-AD^{+}}$ each column sums to zero since ${\displaystyle AD^{+}}$ is left stochastic.

For a non-symmetric adjacency matrix of a directed graph, one also needs to choose indegree or outdegree for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree left normalized Laplacian	In-Degree matrix	In-Degree right normalized Laplacian
${\textstyle \left({\begin{array}{rrr}0&1&0\\0&0&2\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&2&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&0\\0&1&-1\\-1&0&1\\\end{array}}\right)}$

The left out-degree normalized Laplacian with row-sums all 0 relates to right stochastic ${\displaystyle D_{\text{out}}^{+}A}$ , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic ${\displaystyle AD_{\text{in}}^{+}}$.

Negative weights present several challenges for normalisation:

• The presence of negative weights may naturally result in zero row- and/or column-sums for non-isolated vertices. A vertex with a large row-sum of positive weights and equally negatively large row-sum of negative weights, together summing up to zero, could be considered a heavy node and both large values scaled, while the diagonal entry remains zero, like for a isolated vertex.
• Negative weights may also give negative row- and/or column-sums, so that the corresponding diagonal entry in the non-normalized Laplacian matrix would be negative and a positive square root needed for the symmetric normalization would not exist.
• Arguments can be made to take the absolute value of the row- and/or column-sums for the purpose of normalization, thus treating a possible value -1 as a legitimate unit entry of the main diagonal of the normalized Laplacian matrix.

The generalized Laplacian ${\displaystyle Q}$ is defined as:[3]

${\displaystyle {\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}}$

Notice the ordinary Laplacian is a generalized Laplacian.

Entries of the adjacency matrix can be complex-valued, in which case the notion of the matrix symmetry needs to be replaced with a Hermitian matrix. Magnetic Laplacian for a directed graph with real weights ${\displaystyle w_{ij}}$ is constructed as the Hadamard product of the real symmetric matrix of the symmetrized Laplacian and the Hermitian phase matrix with the complex entries

${\displaystyle \gamma _{q}(i,j)=e^{i2\pi q(w_{ij}-w_{ji})}}$

which encode the edge direction into the phase in the complex plane. In the context of quantum physics, the magnetic Laplacian can be interpreted as the operator that describes the phenomenology of a free charged particle on a graph, which is subject to the action of a magnetic field and the parameter ${\displaystyle q}$ is called electric charge.[4] In the following example ${\displaystyle q=1/4}$:

Adjacency matrix	Symmetrized Laplacian	Phase matrix	Magnetic Laplacian
${\textstyle \left({\begin{array}{rrrr}0&1&0&0\\1&0&1&0\\0&0&0&0\\0&0&1&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-1&0\\0&-1&2&-1\\0&0&-1&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}1&1&1&1\\1&1&i&1\\1&-i&1&-i\\1&1&i&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrr}2&-2&0&0\\-2&3&-i&0\\0&i&2&i\\0&0&-i&1\\\end{array}}\right)}$

The deformed Laplacian is commonly defined as

${\displaystyle \Delta (s)=I-sA+s^{2}(D-I)}$

where I is the identity matrix, A is the adjacency matrix, D is the degree matrix, and s is a (complex-valued) number. [5]
The standard Laplacian is just ${\textstyle \Delta (1)}$ and ${\textstyle \Delta (-1)=D+A}$ is the signless Laplacian.

The signless Laplacian is defined as

${\displaystyle Q=D+A}$

where ${\displaystyle D}$ is the degree matrix, and ${\displaystyle A}$ is the adjacency matrix.[6] Like the signed Laplacian ${\displaystyle L}$, the signless Laplacian ${\displaystyle Q}$ also is positive semi-definite as it can be factored as

${\displaystyle Q=RR^{\textsf {T}}}$

where ${\textstyle R}$ is the incidence matrix. ${\displaystyle Q}$ has a 0-eigenvector if and only if it has a bipartite connected component other than isolated vertices. This can be shown as

${\displaystyle \mathbf {x} ^{\textsf {T}}Q\mathbf {x} =\mathbf {x} ^{\textsf {T}}RR^{\textsf {T}}\mathbf {x} \implies R^{\textsf {T}}\mathbf {x} =\mathbf {0} .}$

This has a solution where ${\displaystyle \mathbf {x} \neq \mathbf {0} }$ if and only if the graph has a bipartite connected component.

An analogue of the Laplacian matrix can be defined for directed multigraphs.[7] In this case the Laplacian matrix L is defined as

${\displaystyle L=D-A}$

where D is a diagonal matrix with D_i,i equal to the outdegree of vertex i and A is a matrix with A_i,j equal to the number of edges from i to j (including loops).