Elin Tinnert: Laplacian Matrices as a Tool for Spectral Clustering

Abstract.

A graph can illustrate patterns in data. Clusters in a graph show which of its vertices are closely related. The Laplacian matrix is a powerful matrix that one can associate with a graph. Spectral analysis studies the relations between properties of a graph and eigenvalues of its Laplacian matrix. In this thesis, basic facts about the Laplacian matrix will be introduced and an investigation of its use in the study of clusters will be performed. We derive an approximation of a clustering method called RatioCut for finding two clusters in a graph, which uses the eigenvector of the second smallest eigenvalue as an indicator. We give examples that illustrate the method.