`laplacian`

Laplacian matrix of a graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

L = laplacian(G)

Returns the Laplacian: the degree matrix minus the adjacency matrix.

Description

Each row of L sums to zero, so the vector of ones is an eigenvector with eigenvalue 0. The number of zero eigenvalues equals the number of connected components, and the second smallest eigenvalue measures how well connected the graph is. The eigenvectors are used in spectral partitioning and graph drawing.

Input arguments

G: A graph.

Output arguments

L: Symmetric numnodes(G)-by-numnodes(G) matrix with node degrees on the diagonal and -1 where two nodes are adjacent.

Example

Connectivity from eigenvalues

G = graph([1 2 4], [2 3 5]);
L = laplacian(G);
ev = eig(L)'
sum(abs(ev) < 1e-10)
[~, sizes] = conncomp(G)

Output

ev = 1×5

   -0.0000         0    1.0000    2.0000    3.0000
ans = 2
sizes = 1×2

     3     2

Notes

MatLivre returns full (dense) matrices here, where MATLAB returns sparse ones. Values and sizes are the same.

laplacian