Spectral clustering methods use eigenvectors for data segmentation, where
the underlying matrix reflects the similarity structure in the data points.
Piecewise constant eigenvectors are considered as indicators of a partition.
We will call its components spectral clusters or classes. Main differences
in the methods concern the concrete type of matrix and the utilization of the eigenstructure. The methods are
motivated by equivalence properties of spectral clusters and the fact that spectral clusters are solutions to suitable
optimization criteria. \newline
In the present paper we give a very general presentation of spectral
clustering and a corresponding segmentation criterion, which includes the
mentioned methods as special cases. Additionally we characterize spectral
clusters in terms of hitting times and give a novel segmentation criterion
based on hitting times. We achieve this by utilizing the similarity
structure of the data to define the transition matrix P of a Markov chain
which is used for spectral clustering. The result is due to the fact that
the eigenvectors of P coincide with those of its fundamental matrix, whose
entries may be interpreted in terms of hitting times}).