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 Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method. The Laplacian matrix relates to many functional graph properties. Kirchhoff's theorem can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the Fiedler vector — 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 the construction of low-dimensional embeddings that appear in many machine learning applications and determines a spectral layout in graph drawing. Graph-based signal processing is based on the graph Fourier transform that extends the traditional discrete Fourier transform by substituting the standard basis of complex sinusoids 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 is more common in applications for an edge-weighted graph, i.e., with weights on its edges — the entries of the graph adjacency matrix. Spectral graph theory 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 G {\displaystyle G} with n {\displaystyle n} vertices v 1 , … , v n {\displaystyle v_{1},\ldots ,v_{n}} , its Laplacian matrix L n × n {\textstyle L_{n\times n}} is defined element-wise as
L i , j := { deg ( v i ) if i = j − 1 if i ≠ j and v i is adjacent to v j 0 otherwise , {\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
L = D − A , {\displaystyle L=D-A,}
where D is the degree matrix, and A is the graph's adjacency matrix. Since G {\textstyle G} is a simple graph, A {\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.
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 graphs, either the indegree or outdegree might be used, depending on the application, as in the following example:
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 indegree or outdegree has been used.
Laplacian matrix for an undirected graph via the oriented incidence matrix The | v | × | e | {\textstyle |v|\times |e|} oriented incidence matrix B with element Bve for the vertex v and the edge e (connecting vertices v i {\textstyle v_{i}} and v j {\textstyle v_{j}} , with i ≠ j) is defined by
… excerpt ends here. Continue reading the full article.
