Laplacian Matrix
A matrix, commonly L = D - A, that combines graph degree and adjacency information for spectral analysis of connectivity structure.
The graph Laplacian is not merely another representation of the adjacency matrix. Its eigenstructure carries information about connected components, cuts, and diffusion behavior.
For an undirected graph, the multiplicity of the zero eigenvalue is tied to the number of connected components. The second-smallest eigenvalue and its Fiedler vector are central to spectral partitioning.
Numerical Side
Dense eigendecomposition is a poor fit for large sparse graphs. Most applications need only a small number of extreme eigenpairs, making sparse iterative solvers, normalization choice, and edge-weight scaling important.
Unnormalized, symmetric-normalized, and random-walk Laplacians are not interchangeable.
Source
- https://fanchung.ucsd.edu/research/cb/ch1.pdf