Spectral clustering and its use in bioinformatics (Q879406)

The authors formulate a discrete optimization problem that gives a simple derivation of a widely used class of spectral clustering algorithms. These algorithms bundle objects into groups of similar objects, using the eigendecomposition of a matrix derived from the (real symmetric) matrix \(W=(w_{ij})\), where, for \(i\neq j\), \(w_{ij}\) is a measure of the similarity of the \(i\)th and \(j\)th objects, and \(w_{ii}=0\). The objects are regarded as vertices of an undirected graph. The authors' approach helps explain the difference observed between methods based on the normalized and unnormalized graph Laplacian. A numerical illustration is given using microarray datasets published by cancer researchers.