Abstract

This chapter introduces the definitions for different formulations of graph Laplacians and specific procedures for several kinds of spectral clustering algorithms. It analyzes the spectrum of both unnormalized and normalized Laplacian matrices. The word spectral is used to denote the fact that the clustering results are obtained by analyzing the spectrum of the graph Laplacian. The Laplacian eigenmap algorithm is a very successful method for dimensionality reduction and is closely related to spectral clustering. One of the most popular dimensionality reduction algorithms is Principal Component Analysis which gives the solution by projecting the original high-dimensional data onto the low-dimensional linear subspace spanned by the leading eigenvectors of the data’s covariance matrix. The basic idea of Laplacian eigenmap is also based on spectral graph theory. The general spectral clustering method needs to construct an adjacency matrix and calculate the eigen-decomposition of the corresponding Laplacian matrix.
Original languageEnglish (US)
Title of host publicationData Clustering
Subtitle of host publicationAlgorithms and Applications
EditorsCharu C. Aggarwal, Chandan K. Reddy
PublisherChapman and Hall/CRC
Pages177-200
ISBN (Electronic)9781315373515
DOIs
StatePublished - 2014

Publication series

NameChapman & Hall/CRC Data Mining and Knowledge Discovery Series

Fingerprint

Dive into the research topics of 'Spectral Clustering'. Together they form a unique fingerprint.

Cite this