In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the Laplacian matrix, also called the
graph Laplacian
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Lapl ...
,
admittance matrix
In power engineering, nodal admittance matrix (or just admittance matrix) or Y Matrix or Ybus is an ''N x N'' matrix describing a linear power system with ''N'' buses. It represents the nodal admittance of the buses in a power system. In realist ...
, Kirchhoff matrix or
discrete Laplacian, is a
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
representation of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
. Named after
Pierre-Simon Laplace
Pierre-Simon, marquis de Laplace (; ; 23 March 1749 – 5 March 1827) was a French scholar and polymath whose work was important to the development of engineering, mathematics, statistics, physics, astronomy, and philosophy. He summarized ...
, the graph Laplacian matrix can be viewed as a matrix form of the negative
discrete Laplace operator
In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph (having a finite number of edges and vertice ...
on a graph approximating the negative continuous
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
obtained by the
finite difference method
In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating derivatives with finite differences. Both the spatial domain and time interval (if applicable) are di ...
.
The Laplacian matrix relates to many useful properties of a graph. Together with
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time f ...
, it can be used to calculate the number of
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s for a given graph. The
sparsest cut of a graph can be approximated through the
Fiedler vector
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ''G'' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of ''G''. This eigenvalue ...
— the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established by
Cheeger's inequality. The
spectral decomposition of the Laplacian matrix allows constructing
low dimensional embeddings that appear in many
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
applications and determines a
spectral layout
Spectral layout is a class of algorithm for drawing graphs. The layout uses the eigenvectors of a matrix, such as the Laplace matrix of the graph, as Cartesian coordinate
A Cartesian coordinate system (, ) in a plane is a coordinate system ...
in
graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...
. Graph-based
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...
is based on the
graph Fourier transform
In mathematics, the graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical Fourier Transform, the eigenvalues represent frequenci ...
that extends the traditional
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex- ...
by substituting the standard basis of
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
sinusoid
A sine wave, sinusoidal wave, or just sinusoid is a mathematical curve defined in terms of the ''sine'' trigonometric function, of which it is the graph. It is a type of continuous wave and also a smooth periodic function. It occurs often in ma ...
s for eigenvectors of the Laplacian matrix of a graph corresponding to the signal.
The Laplacian matrix is the easiest to define for a
simple graph, but more common in applications for an
edge-weighted graph, i.e., with weights on its edges — the entries of the graph
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
.
Spectral graph theory
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix ...
relates properties of a graph to a spectrum, i.e., eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. Imbalanced weights may undesirably affect the matrix spectrum, leading to the need of normalization — a column/row scaling of the matrix entries — resulting in normalized adjacency and Laplacian matrices.
Definitions for ''simple graphs''
Laplacian matrix
Given a
simple graph with
vertices
, its Laplacian matrix
is
defined element-wise as
:
or equivalently by the matrix
:
where ''D'' is the
degree matrix In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex.. It is used togeth ...
and ''A'' is the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of the graph. Since
is a simple graph,
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.
We observe for the undirected graph that both the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
and the Laplacian matrix are symmetric, and that row- and column-sums of the Laplacian matrix are all zeros.
For
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, either the
indegree or outdegree might be used, depending on the application, as in the following example:
In the directed graph, both the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
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.
Symmetric Laplacian via the incidence matrix
The
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
''B'' with element ''B''
''ve'' for the vertex ''v'' and the edge ''e'' (connecting vertexes
and
, with ''i'' > ''j'') is defined by
:
Even though the edges in this definition are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian
matrix ''L'' defined as
:
where
is the
matrix transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
of ''B''.
{, class="wikitable"
!
Undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
!
Incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
! Laplacian matrix
, -
,
100px
,
,
An alternative product
defines the so-called
''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
In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as ...
is primarily developed for undirected graphs with symmetric adjacency and Laplacian matrixes. 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
of the original directed graph and its
matrix transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
, where the zero and one entries of
are treated as logical, rather than numerical, values, as in the following example:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Symmetrized adjacency
! Symmetric Laplacian matrix
, -
,
,
,
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:
:
where
is the
Moore–Penrose inverse
In mathematics, and in particular linear algebra, the Moore–Penrose inverse of a matrix is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Pe ...
.
The elements of
are thus given by
:
The symmetrically normalized Laplacian matrix is symmetric if and only if the adjacency matrix is symmetric.
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Degree matrix
! Normalized Laplacian
, -
,
,
,
For a non-symmetric adjacency matrix of a directed graph, either of
indegree and outdegree can be used for normalization:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Out-Degree matrix
! Out-Degree normalized Laplacian
! In-Degree matrix
! In-Degree normalized Laplacian
, -
,
,
,
,
,
Left (random-walk) and right normalized Laplacians
The left (random-walk) normalized Laplacian matrix is defined as:
:
where
is the
Moore–Penrose inverse
In mathematics, and in particular linear algebra, the Moore–Penrose inverse of a matrix is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Pe ...
.
The elements of
are given by
:
Similarly, the right normalized Laplacian matrix is defined as
:
.
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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Degree matrix
! Left normalized Laplacian
! Right normalized Laplacian
, -
,
,
,
,
The example also demonstrates that if
has no isolated vertices, then
right stochastic and hence is the matrix of a
random walk
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
, so that the left normalized Laplacian
has each row summing to zero. Thus we sometimes alternatively call
the
random-walk normalized Laplacian. In the less uncommonly used right normalized Laplacian
each column sums to zero since
is
left stochastic.
For a non-symmetric adjacency matrix of a directed graph, one also needs to choose
indegree or outdegree for normalization:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Out-Degree matrix
! Out-Degree left normalized Laplacian
! In-Degree matrix
! In-Degree right normalized Laplacian
, -
,
,
,
,
,
The left out-degree normalized Laplacian with row-sums all 0 relates to
right stochastic , while the right in-degree normalized Laplacian with column-sums all 0 contains
left stochastic .
Definitions for graphs with weighted edges
Common in applications graphs with weighted edges are conveniently defined by their adjacency matrices where values of the entrees are numeric and no longer limited to zeros and ones. In
spectral clustering
In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as ...
and graph-based
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...
, where graph vertices represent data points, the edge weights can be computed, e.g., as inversely proportional to the
distances
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
between pairs of data points, leading to all weights being non-negative with larger values informally corresponding to more similar pairs of data points. Using correlation and anti-correlation between the data points naturally leads to both positive and negative weights. Most definitions for simple graphs are trivially extended to the standard case of non-negative weights, while negative weights require more attention, especially in normalization.
Laplacian matrix
The Laplacian matrix is defined by
:
where ''D'' is the
degree matrix In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex.. It is used togeth ...
and ''A'' is the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of the graph.
For
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, either the
indegree or outdegree might be used, depending on the application, as in the following example:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! In-Degree matrix
! In-Degree Laplacian
! Out-Degree matrix
! Out-Degree Laplacian
, -
,
,
,
,
,
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.
Symmetric Laplacian via the incidence matrix
For graphs with weighted edges one can define a weighted incidence matrix ''B'' and use it to construct the corresponding symmetric Laplacian as
. An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using the
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
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
Mechanics (from Ancient Greek: μηχανική, ''mēkhanikḗ'', "of machines") is the area of mathematics and physics concerned with the relationships between force, matter, and motion among physical objects. Forces applied to objects r ...
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
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
''B'' with element ''B''
''ve'' for the vertex ''v'' and the edge ''e'' (connecting vertexes
and
, with ''i'' > ''j'') defined by
:
We now also define a diagonal
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
matrix ''L'' defined as
:
where
is the
matrix transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
of ''B''.
The construction is illustrated in the following example, where every edge
is assigned the weight value ''i'', with
{, class="wikitable"
!
Undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
!
Incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
! Edge weights
! Laplacian matrix
, -
,
100px
,
,
,
Symmetric Laplacian for a directed graph
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
of the original directed graph and its
matrix transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
as in the following example:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Symmetrized adjacency matrix
! Symmetric Laplacian matrix
, -
,
,
,
where the zero and one entries of
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:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Out-Degree matrix
! Out-Degree Laplacian
! In-Degree matrix
! In-Degree Laplacian
, -
,
,
,
,
,
The sum of the out-degree Laplacian transposed and the in-degree Laplacian equals to the symmetric Laplacian matrix.
Laplacian matrix normalization
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.
Symmetrically normalized Laplacian
The symmetrically normalized Laplacian is defined as
:
where ''L'' is the unnormalized Laplacian, ''A'' is the adjacency matrix, ''D'' is the degree matrix, and
is the
Moore–Penrose inverse
In mathematics, and in particular linear algebra, the Moore–Penrose inverse of a matrix is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Pe ...
. Since the degree matrix ''D'' is diagonal, its reciprocal square root
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:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! In-Degree matrix
! In-Degree normalized Laplacian
! Out-Degree matrix
! Out-Degree normalized Laplacian
, -
,
,
,
,
,
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
:
using the weightless
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
''B'' and the diagonal
matrix ''W'' containing the edge weights and defining the new
weighted incidence matrix
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
in the row corresponding to ''u'', an entry
in the row corresponding to ''v'', and has 0 entries elsewhere.
Random walk normalized Laplacian
The random walk normalized Laplacian is defined as
:
where ''D'' is the degree matrix. Since the degree matrix ''D'' is diagonal, its inverse
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
to 0. The matrix elements of
are given by
:
The name of the random-walk normalized Laplacian comes from the fact that this matrix is
, where
is simply the transition matrix of a random walker on the graph, assuming non-negative weights. For example, let
denote the i-th
standard basis
In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as \mathbb^n or \mathbb^n) is the set of vectors whose components are all zero, except one that equals 1. For example, in the c ...
vector. Then
is a
probability vector
In mathematics and statistics, a probability vector or stochastic vector is a vector with non-negative entries that add up to one.
The positions (indices) of a probability vector represent the possible outcomes of a discrete random variable, and ...
representing the distribution of a random walker's locations after taking a single step from vertex
; i.e.,
. More generally, if the vector
is a probability distribution of the location of a random walker on the vertices of the graph, then
is the probability distribution of the walker after
steps.
The random walk normalized Laplacian can also be called the left normalized Laplacian
since the normalization is performed by multiplying the Laplacian by the normalization matrix
on the left. It has each row summing to zero since
is
right stochastic, assuming all the weights are non-negative.
In the less uncommonly used right normalized Laplacian
each column sums to zero since
is
left stochastic.
For a non-symmetric adjacency matrix of a directed graph, one also needs to choose
indegree or outdegree for normalization:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Out-Degree matrix
! Out-Degree left normalized Laplacian
! In-Degree matrix
! In-Degree right normalized Laplacian
, -
,
,
,
,
,
The left out-degree normalized Laplacian with row-sums all 0 relates to
right stochastic , while the right in-degree normalized Laplacian with column-sums all 0 contains
left stochastic .
Negative weights
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.
Properties
For an (undirected) graph ''G'' and its Laplacian matrix ''L'' with
eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
:
* ''L'' is
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
.
* ''L'' is
positive-semidefinite (that is
for all
). This can be seen from the fact that the Laplacian is symmetric and
diagonally dominant
In mathematics, a square matrix is said to be diagonally dominant if, for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row ...
.
* ''L'' is an
M-matrix In mathematics, especially linear algebra, an ''M''-matrix is a ''Z''-matrix with eigenvalues whose real parts are nonnegative. The set of non-singular ''M''-matrices are a subset of the class of ''P''-matrices, and also of the class of inverse-p ...
(its off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative).
* Every row sum and column sum of ''L'' is zero. Indeed, in the sum, the degree of the vertex is summed with a "−1" for each neighbor.
* In consequence,
, because the vector
satisfies
This also implies that the Laplacian matrix is singular.
* The number of
connected components in the graph is the dimension of the
nullspace
In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kernel of ...
of the Laplacian and the
algebraic multiplicity
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
of the 0 eigenvalue.
* The smallest non-zero eigenvalue of ''L'' is called the
spectral gap
In mathematics, the spectral gap is the difference between the moduli of the two largest eigenvalues of a matrix or operator; alternately, it is sometimes taken as the smallest non-zero eigenvalue. Various theorems relate this difference to othe ...
.
* The second smallest eigenvalue of ''L'' (could be zero) is the
algebraic connectivity
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ''G'' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of ''G''. This eigenvalue i ...
(or
Fiedler value) of ''G'' and approximates the
sparsest cut of a graph.
* The
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
is an operator on the n-dimensional vector space of functions
, where
is the vertex set of G, and
.
* When G is
k-regular, the normalized Laplacian is:
, where A is the adjacency matrix and I is an identity matrix.
* For a graph with multiple
connected components, ''L'' is a
block diagonal
In mathematics, a block matrix or a partitioned matrix is a matrix that is '' interpreted'' as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original m ...
matrix, where each block is the respective Laplacian matrix for each component, possibly after reordering the vertices (i.e. ''L'' is permutation-similar to a block diagonal matrix).
* The trace of the Laplacian matrix ''L'' is equal to
where
is the number of edges of the considered graph.
* Now consider an eigendecomposition of
, with unit-norm eigenvectors
and corresponding eigenvalues
:
:
Because
can be written as the inner product of the vector
with itself, this shows that
and so the eigenvalues of
are all non-negative.
* All eigenvalues of the normalized symmetric Laplacian satisfy 0 = μ
0 ≤ … ≤ μ
n−1 ≤ 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs.
* One can check that:
:
,
i.e.,
is
similar to the normalized Laplacian
. For this reason, even if
is in general not symmetric, it has real eigenvalues — exactly the same as the eigenvalues of the normalized symmetric Laplacian
.
Interpretation as the discrete Laplace operator approximating the continuous Laplacian
The graph Laplacian matrix can be further viewed as a matrix form of the negative
discrete Laplace operator
In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph (having a finite number of edges and vertice ...
on a graph approximating the negative continuous
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
operator obtained by the
finite difference method
In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating derivatives with finite differences. Both the spatial domain and time interval (if applicable) are di ...
.
(See
Discrete Poisson equation
In mathematics, the discrete Poisson equation is the finite difference analog of the Poisson equation. In it, the discrete Laplace operator takes the place of the Laplace operator. The discrete Poisson equation is frequently used in numerical an ...
) In this interpretation, every graph vertex is treated as a grid point; the local connectivity of the vertex determines the finite difference approximation
stencil
Stencilling produces an image or pattern on a surface, by applying pigment to a surface through an intermediate object, with designed holes in the intermediate object, to create a pattern or image on a surface, by allowing the pigment to reach ...
at this grid point, the grid size is always one for every edge, and there are no constraints on any grid points, which corresponds to the case of the homogeneous
Neumann boundary condition
In mathematics, the Neumann (or second-type) boundary condition is a type of boundary condition, named after Carl Neumann.
When imposed on an ordinary or a partial differential equation, the condition specifies the values of the derivative appl ...
, i.e., free boundary. Such an interpretation allows one, e.g., generalizing the Laplacian matrix to the case of graphs with an infinite number of vertices and edges, leading to a Laplacian matrix of an infinite size.
Generalizations and extensions of the Laplacian matrix
Generalized Laplacian
The generalized Laplacian
is defined as:
:
Notice the ordinary Laplacian is a generalized Laplacian.
Magnetic Laplacian
Entries of the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
can be complex-valued, in which case the notion of the matrix symmetry needs to be replaced with a
Hermitian matrix
In mathematics, a Hermitian matrix (or self-adjoint matrix) is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the -th row and -th column is equal to the complex conjugate of the element in the -th ...
. Magnetic Laplacian for a directed graph with real weights
is constructed as the
Hadamard product of the
real symmetric matrix of the symmetrized Laplacian and the Hermitian phase matrix with the
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
entries
:
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
is called electric charge.
In the following example
:
{, class="wikitable"
!
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
! Symmetrized Laplacian
! Phase matrix
! Magnetic Laplacian
, -
,
,
,
,
Deformed Laplacian
The deformed Laplacian is commonly defined as
:
where ''I'' is the identity matrix, ''A'' is the adjacency matrix, ''D'' is the degree matrix, and ''s'' is a (complex-valued) number.
The standard Laplacian is just
and
is the signless Laplacian.
Signless Laplacian
The signless Laplacian is defined as
:
where
is the degree matrix, and
is the adjacency matrix. Like the signed Laplacian
, the signless Laplacian
also is positive semi-definite as it can be factored as
:
where
is the incidence matrix.
has a 0-eigenvector if and only if it has a bipartite connected component other than isolated vertices. This can be shown as
:
This has a solution where
if and only if the graph has a bipartite connected component.
Directed multigraphs
An analogue of the Laplacian matrix can be defined for directed multigraphs.
In this case the Laplacian matrix ''L'' is defined as
:
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).
Open source software implementations
*
SciPy
SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing.
SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signal ...
*
NetworkX
NetworkX is a Python library for studying graphs and networks. NetworkX is free software released under the BSD-new license.
Features
* Classes for graphs and digraphs.
* Conversion of graphs to and from several formats.
* Ability to con ...
Application software
*
scikit-learn
scikit-learn (formerly scikits.learn and also known as sklearn) is a free software machine learning library for the Python programming language.
It features various classification, regression and clustering algorithms including support-vector ...
Spectral Clustering
* PyGSP: Graph Signal Processing in Python
* megaman: Manifold Learning for Millions of Points
* smoothG
* Laplacian Change Point Detection for Dynamic Graphs (KDD 2020)
* LaplacianOpt (A Julia Package for Maximizing Laplacian's Second Eigenvalue of Weighted Graphs)
* LigMG (Large Irregular Graph MultiGrid)
* Laplacians.jl
See also
*
Stiffness matrix
In the finite element method for the numerical solution of elliptic partial differential equations, the stiffness matrix is a matrix that represents the system of linear equations that must be solved in order to ascertain an approximate solution ...
*
Resistance distance
In graph theory, the resistance distance between two vertices of a simple, connected graph, , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to , with each edge being replaced b ...
*
Transition rate matrix
Transition or transitional may refer to:
Mathematics, science, and technology Biology
* Transition (genetics), a point mutation that changes a purine nucleotide to another purine (A ↔ G) or a pyrimidine nucleotide to another pyrimidine (C ↔ ...
*
Calculus on finite weighted graphs In mathematics, calculus on finite weighted graphs is a discrete calculus for functions whose domain is the vertex set of a graph with a finite number of vertices and weights associated to the edges. This involves formulating discrete operators on ...
*
Graph Fourier transform
In mathematics, the graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical Fourier Transform, the eigenvalues represent frequenci ...
References
{{Matrix classes
Algebraic graph theory
Matrices
Numerical differential equations