Laplacian matrix

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be used to find many other properties of the graph; see spectral graph theory. Cheeger's inequality from Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.

Definition

Given a simple graph G with n vertices, its Laplacian matrix $L:=(\ell _{{i,j}})_{{n\times n}}$ is defined as:^[1]

$L=D-A.$

That is, it is the difference of the degree matrix D and the adjacency matrix A of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.

From the definition it follows that:

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

where deg(v_i) is degree of the vertex i.

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

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

Example

Here is a simple example of a labeled graph and its Laplacian matrix.

Labeled graph	Degree matrix	Adjacency matrix	Laplacian matrix
	$\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)$	$\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)$	$\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)$

Properties

For a graph G and its Laplacian matrix L with eigenvalues $\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{{n-1}}$ :

L is always positive-semidefinite ( $\forall i,\lambda _{i}\geq 0;\lambda _{0}=0$ ). This is verified in the following Incidence matrix section.
The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
L is an M-matrix.
$\lambda _{0}$ is always 0 because every Laplacian matrix has an eigenvector ${\mathbf {v}}_{0}=[1,1,\dots ,1]$ that, for each row, adds the corresponding node's degree (from the diagonal) to a "-1" for each neighbor so that $L{\mathbf {v}}_{0}=0.$
The smallest non-zero eigenvalue of L is called the spectral gap.

The second smallest eigenvalue of L is the algebraic connectivity (or Fiedler value) of G.

The Laplacian is an operator on the function of g. When G is k-regular,

$\ell =I-{\frac {1}{k}}A$ ,

where A is the adjacency matrix of G and I is an identity matrix. All matrices are n × n where n is the number of vertices in G.

For a graph with multiple connected components, L is a block diagonal matrix, where each block is the respective Laplacian matrix for each component.

Incidence matrix

Define an $|e|$ x $|v|$ oriented incidence matrix M with element M_ev for edge e (connecting vertex i and j, with i > j) and vertex v given by

$M_{{ev}}=\left\{{\begin{array}{rl}1,&{\text{if}}\,v=i\\-1,&{\text{if}}\,v=j\\0,&{\text{otherwise}}.\end{array}}\right.$

Then the Laplacian matrix L satisfies

$L=M^{{\text{T}}}M\,,$

where $M^{{\text{T}}}$ is the matrix transpose of M.

Now consider an eigendecomposition of $L$ , with unit-norm eigenvectors ${\mathbf {v}}_{i}$ and corresponding eigenvalues $\lambda _{i}$ :

${\begin{aligned}\lambda _{i}&={\mathbf {v}}_{i}^{T}L{\mathbf {v}}_{i}\\&={\mathbf {v}}_{i}^{T}M^{T}M{\mathbf {v}}_{i}\\&=(M{\mathbf {v}}_{i})^{T}(M{\mathbf {v}}_{i}).\\\end{aligned}}$

Because $\lambda _{i}$ can be written as the inner product of the vector $M{\mathbf {v}}_{i}$ with itself, this shows that $\lambda _{i}\geq 0$ and so the eigenvalues of $L$ are all non-negative.

Deformed Laplacian

The deformed Laplacian is commonly defined as

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

where I is the unit matrix, A is the adjacency matrix, and D is the degree matrix, and s is a (complex-valued) number. Note that the standard Laplacian is just $\Delta (1)$ .

Symmetric normalized Laplacian

The symmetric normalized Laplacian (a.k.a. normalized Laplacian) is defined as

$L^{{norm}}:=I-D^{{-1/2}}AD^{{-1/2}}$

where A is the adjacency matrix and D is the degree matrix. Since the degree matrix D is diagonal, its reciprocal square root $D^{{-1/2}}$ is simply defined as a diagonal matrix, having diagonal entries which are the reciprocals of the positive square roots of the corresponding positive diagonal entries of D. The symmetric normalized Laplacian is a symmetric matrix.

$L^{{norm}}=SS^{{*}}$ ,

where S is the 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 ${\frac {1}{{\sqrt d}_{{u}}}}$ in the row corresponding to u, an entry $-{\frac {1}{{\sqrt d}_{{v}}}}$ in the row corresponding to v, and has 0 entries elsewhere. (Note: $S^{{*}}$ denotes the transpose of S).

The symmetric normalized Laplacian can also be written as

$L^{{norm}}=I-D^{{-1/2}}AD^{{-1/2}}=D^{{-1/2}}LD^{{-1/2}}.$

All eigenvalues of the normalized Laplacian are real and non-negative. In fact,if λ is an eigenvalue of L, then 0 ≤ λ ≤ 2. These eigenvalues (known as spectra of the normalized Laplacian) relate well to other graph invariants for general graphs.^[2]

Since $L^{{norm}}$ is symmetric, its eigenvalues are real and non-negative. We can use its characterization in terms of Rayleigh quotient of $L^{{norm}}$ .

Let g be an arbitrary function which assigns to each vertex v of G a real value g(v). We can treat g as a column vector.

${\begin{aligned}{\frac {g,L_{{g}}^{{norm}}}{g,g}}&={\frac {g,D^{{-1/2}}LD^{{-1/2}}g}{g,g}}\\&={\frac {f,Lf}{D^{{1/2}}f,D^{{1/2}}f}}\\&={\frac {\sum _{{u~v}}(f(u)-f(v))^{2}}{\sum _{{v}}f(v)^{2}d_{{v}}}},\end{aligned}}$

where $g=D^{{1/2}}f$ and $\sum _{{u~v}}$ denotes the sum over all unordered pairs {u,v} for which u and v are adjacent. $\sum _{{u,v}}(f(u)-f(v))^{2}$ is called the Dirichlet sum of G. The left hand side of the equation is Rayleigh quotient.

The eigenvalues of $L^{{norm}}$ by $0=\lambda _{0}\leq \lambda _{1}\leq \cdots \lambda _{{n-1}}$ . the set of $\lambda _{i}$ is usually called the spectrum of $L^{{norm}}$ Let 1 be the function which assumes the value 1 on each vertex. Then $D^{{1/2}}1$ is an eigenfunction of $L^{{norm}}$ with eigenvalue 0.

^[3]

Random walk normalized Laplacian

The random walk normalized Laplacian is defined as

$T:=D^{{-1}}A$

where A is the adjacency matrix and D is the degree matrix. Since the degree matrix D is diagonal, its inverse $D^{{-1}}$ is simply defined as a diagonal matrix, having diagonal entries which are the reciprocals of the corresponding positive diagonal entries of D. The name of this operator comes from the fact that, indeed, $T$ is the transition matrix of a standard random walk on the given graph.

One can check that

$T=D^{{-{\frac 12}}}\left(I-L^{{norm}}\right)D^{{{\frac 12}}}$ ,

i.e., $T$ is similar to a scalar perturbation of the normalized Laplacian $L^{{norm}}$ . For this reason, even if $T$ is in general not hermitian, it has real eigenvalues. Indeed, its eigenvalues agree with those of $L^{{norm}}$ (which is hermitian), up to a mirroring in the point $1/2$ .

Random walks on graphs

As an aside about random walks on graphs, consider a simple undirected graph. Consider the probability that a walk is at a vertex i at time t comes from vertex j at time t-1 (assuming a uniform chance of taking a step along any of the edges attached to vertex j):

$p_{i}(t)=\sum _{j}{\frac {A_{{ij}}}{deg(v_{j})}}p_{j}(t-1),$

or in matrix-vector notation:

$p(t)=AD^{{-1}}p(t-1).$

(At equilibrium where $t\rightarrow \infty$ , this is written as $p=AD^{{-1}}p$ ).

We can rewrite this relation as

${\begin{aligned}D^{{-{\frac 12}}}p(t)&=D^{{-{\frac 12}}}AD^{{-1}}p(t-1)\\&=\left[D^{{-{\frac 12}}}AD^{{-{\frac 12}}}\right]D^{{-{\frac 12}}}p(t-1).\end{aligned}}$

$A_{{reduced}}\equiv D^{{-{\frac 12}}}AD^{{-{\frac 12}}}$ is a symmetric matrix called the reduced adjacency matrix. So, taking steps on this random walk requires repeated multiplication of $A_{{reduced}}$ , which is a simple operation because $A_{{reduced}}$ is symmetric.

Interpretation as the discrete Laplace operator

The Laplacian matrix can be interpreted as a matrix representation of a particular case of the negative discrete Laplace operator. Such an interpretation allows one, e.g., to generalise 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.

To expand upon this, we can describe the change of some element $\phi _{i}$ (with some constant k) as

${\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{{ij}}(\phi _{i}-\phi _{j})\\&=-k\phi _{i}\sum _{j}A_{{ij}}+k\sum _{j}A_{{ij}}\phi _{j}\\&=-k\phi _{i}\ deg(v_{i})+k\sum _{j}A_{{ij}}\phi _{j}\\&=-k\sum _{j}(\delta _{{ij}}\ deg(v_{i})-A_{{ij}})\phi _{j}\\&=-k\sum _{j}(\ell _{{ij}})\phi _{j}.\end{aligned}}$

In matrix-vector notation,

${\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}$

which gives

${\begin{aligned}{\frac {d\phi }{dt}}+kL\phi =0.\end{aligned}}$

Notice that this equation takes the same form as the heat equation, where the matrix L is replacing the Laplacian operator $\nabla ^{2}$ ; hence, the "graph Laplacian".

To find a solution to this differential equation, apply standard techniques for solving a first-order matrix differential equation. That is, write $\phi$ as a linear combination of eigenvectors ${\mathbf {v}}_{i}$ of L (so that $L{\mathbf {v}}_{i}=\lambda _{i}{\mathbf {v}}_{i}$ ), with time-dependent coefficients $c_{i}(t)$ :

${\begin{aligned}\phi =\sum _{i}c_{i}{\mathbf {v}}_{i}.\end{aligned}}$

Plugging into the original expression (note that we will use the fact that because L is a symmetric matrix, its unit-norm eigenvectors ${\mathbf {v}}_{i}$ are orthogonal):

${\begin{aligned}{\frac {d(\sum _{i}c_{i}{\mathbf {v}}_{i})}{dt}}+kL(\sum _{i}c_{i}{\mathbf {v}}_{i})&=0\\\sum _{i}\left[{\frac {dc_{i}}{dt}}{\mathbf {v}}_{i}+kc_{i}L{\mathbf {v}}_{i}\right]&=\\\sum _{i}\left[{\frac {dc_{i}}{dt}}{\mathbf {v}}_{i}+kc_{i}\lambda _{i}{\mathbf {v}}_{i}\right]&=\\{\frac {dc_{i}}{dt}}+k\lambda _{i}c_{i}&=0,\\\end{aligned}}$

whose solution is

${\begin{aligned}c_{i}(t)=c_{i}(0)\exp(-k\lambda _{i}t).\end{aligned}}$

As shown before, the eigenvalues $\lambda _{i}$ of L are non-negative, showing that the solution to the diffusion equation approaches an equilibrium, because it only exponentially decays or remains constant. This also shows that given $\lambda _{i}$ and the initial condition $c_{i}(0)$ , the solution at any time t can be found.^[4]

To find $c_{i}(0)$ for each $i$ in terms of the overall initial condition $c(0)$ , simply project $c(0)$ onto the unit-norm eigenvectors ${\mathbf {v}}_{i}$ ;

$c_{i}(0)=\langle c(0),{\mathbf {v}}_{i}\rangle$ .

In the case of undirected graphs, this works because $L$ is symmetric, and by the spectral theorem, its eigenvectors are all orthogonal. So the projection onto the eigenvectors of $L$ is simply an orthogonal coordinate transformation of the initial condition to a set of coordinates which decay exponentially and independently of each other.

Equilibrium Behavior

To understand $\lim _{{t\to \infty }}\phi (t)$ , note that the only terms $c_{i}(t)=c_{i}(0)\exp(-k\lambda _{i}t)$ that remain are those where $\lambda _{i}=0$ , since

$\lim _{{x\to \infty }}\exp(-k\lambda _{i}t)=\left\{{\begin{array}{rlr}1&{\text{if}}&\lambda _{i}>0\\0&{\text{if}}&\lambda _{i}=0\end{array}}\right\}$

In other words, the equilibrium state of the system is determined completely by the kernel of $L$ . Since by definition, $\sum _{{j}}L_{{ij}}=0$ , the vector ${\mathbf {v}}^{1}$ of all ones is in the kernel. Note also that if there are $k$ disjoint connected components in the graph, then this vector of all ones can be split into the sum of $k$ independent $\lambda =0$ eigenvectors of ones and zeros, where each connected component corresponds to an eigenvector with ones at the elements in the connected component and zeros elsewhere.

The consequence of this is that for a given initial condition $c(0)$ for a graph with $N$ vertices

$\lim _{{t\to \infty }}\phi (t)=\langle c(0),{\mathbf {v^{1}}}\rangle {\mathbf {v^{1}}}$

where

${\mathbf {v^{1}}}={\frac {1}{{\sqrt {N}}}}[1,1,...,1]$

For each vertex $j$ in the graph, this can be rewritten as

$\lim _{{t\to \infty }}\phi (t)_{j}={\frac {1}{N}}\sum _{{i=1}}^{N}c(0)_{i}$

In other words, at steady state, the value of $\phi$ converges to the same value at each of the vertices of the graph, which is the average of the initial values at all of the vertices. Since this is the solution to the heat diffusion equation, this makes perfect sense intuitively. We expect that neighboring elements in the graph will exchange energy until that energy is spread out evenly throughout all of the elements that are connected to each other.

Example of the Operator on a Grid

This GIF shows the progression of diffusion, as solved by the graph laplacian technique. A graph is constructed over a grid, where each pixel in the graph is connected to its 8 bordering pixels. Values in the image then diffuse smoothly to their neighbors over time via these connections. This particular image starts off with three strong point values which spill over to their neighbors slowly. The whole system eventually settles out to the same value at equilibrium.

This section shows an example of a function $\phi$ diffusing over time through a graph. The graph in this example is constructed on a 2D discrete grid, with points on the grid connected to their eight neighbors. Three initial points are specified to have a positive value, while the rest of the values in the grid are zero. Over time, the exponential decay acts to distribute the values at these points evenly throughout the entire grid.

The complete Matlab source code that was used to generate this animation is provided below. It shows the process of specifying initial conditions, projecting these initial conditions onto the eigenvalues of the Laplacian Matrix, and simulating the exponential decay of these projected initial conditions.

N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix
 
%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
   for y = 1:N
       index = (x-1)*N + y;
       for ne = 1:length(dx)
           newx = x + dx(ne);
           newy = y + dy(ne);
           if newx > 0 && newx <= N && newy > 0 && newy <= N
               index2 = (newx-1)*N + newy;
               Adj(index, index2) = 1;
           end
       end
   end
end
 
%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);
 
%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);
 
 
C0V = V'*C0;%Transform the initial condition into the coordinate system 
%of the eigenvectors
for t = 0:0.05:5
   %Loop through times and decay each initial component
   Phi = C0V.*exp(-D*t);%Exponential decay for each component
   Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
   Phi = reshape(Phi, N, N);
   %Display the results and write to GIF file
   imagesc(Phi);
   caxis([0, 10]);
   title(sprintf('Diffusion t = %3f', t));
   frame = getframe(1);
   im = frame2im(frame);
   [imind, cm] = rgb2ind(im, 256);
   if t == 0
      imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); 
   else
      imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
   end
end

As an approximation to the negative continuous Laplacian

The graph Laplacian matrix can be further viewed as a matrix form of an approximation to the negative Laplacian operator obtained by the finite difference method ^{[citation needed]}. In this interpretation, every graph vertex is treated as a grid point; the local connectivity of the vertex determines the finite difference approximation stencil 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, i.e., free boundary.

References

↑ 1.0 1.1 Weisstein, Eric W., "Laplacian Matrix", MathWorld.
↑ Chung, Fan (1992, revised 1997). Spectral Graph Theory. American Mathematical Society. ISBN 0821803158. Check date values in: |date= (help)
↑ Chung, Fan R.K. (1997). Spectral graph theory (Repr. with corr., 2. [pr.] ed.). Providence, RI: American Math. Soc. ISBN 0-8218-0315-8.
↑ Newman, Mark (2010). Networks: An Introduction. Oxford University Press. ISBN 0199206651.

T. Sunada, Discrete geometric analysis, Proceedings of Symposia in Pure Mathematics, (ed. by P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev), 77 (2008), 51-86.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.