Clustering is a fundamental problem in unsupervised learning and a number of different algorithms and methods have emerged over the years.
-means and spectral clustering are two popular methods for clustering analysis.
-means (KM) is proposed to cluster attribute-based data into
numbers of clusters with the minimal distortion [4, 8]. Another well known method, spectral clustering (SC) [18, 20], is also widely adopted in many applications. Unlike KM, SC is specifically developed for graphs, where the data samples are represented as vertices connected by non-negatively weighted undirected edges. The problem of clustering on graphs belongs to another paradigm than the algorithms based on the distortion measure.