Laplacian Matrix

A Laplacian Matrix is a matrix structure that represents a graph.

• AKA: Admittance Matrix, Kirchhoff Matrix.
• See: Affinity Matrix, Eigenvector, Adjacency Matrix, Kirchhoff's Theorem, Spanning Tree (Mathematics).

---

---

References

2016

• (Wikipedia, 2016) ⇒ https://en.wikipedia.org/wiki/Laplacian_matrix Retrieved:2016-6-6.
  • 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. The Laplacian matrix can be used to find many useful properties of graph. Together with Kirchhoff's theorem, it 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 second eigenvalue of its Laplacian by Cheeger's inequality .

2011

• (Wikipedia - Spectral Clustering, 2011-Jun-13) ⇒ http://en.wikipedia.org/wiki/Cluster_analysis#Spectral_clustering
  • QUOTE: Given a set of data points A, the similarity matrix may be defined as a matrix [math]\displaystyle{ S }[/math] where [math]\displaystyle{ S_{ij} }[/math] represents a measure of the similarity between points [math]\displaystyle{ i, j\in A }[/math]. … It partitions points into two sets [math]\displaystyle{ (S_1,S_2) }[/math] based on the eigenvector [math]\displaystyle{ v }[/math] corresponding to the second-smallest eigenvalue of the Laplacian matrix [math]\displaystyle{ L = I - D^{-1/2}SD^{-1/2} }[/math] of [math]\displaystyle{ S }[/math], where [math]\displaystyle{ D }[/math] is the diagonal matrix [math]\displaystyle{ D_{ii} = \sum_{j} S_{ij}. }[/math]

---