The act of creating clusters by segmenting a set
into several parts is ever present in every scientific domain that deals with
interacting or interconnected data.
The formation of clusters consists of distributing a group of
objects into distinct subsets. This process generally
aims to obtain parts of roughly equal size with strong internal
and weak external connections. Clustering using spectral
methods is widely used [1]},
and can be applied to any kind of data
with a suitable similarity metric between them. The theoretical background for this family of methods is based on the balanced graph partitioning problem, with reformulations connecting it also with random walks [2]}, [3]} and perturbation theory [1]}. As opposed to traditional clustering techniques, such as the k-means [5]} and the expectation-maximization algorithm [6]}, spectral methods perform well in nonconvex sample spaces, as they can avoid local minima [7]}. They have therefore been successfully applied in various fields of data clustering, such as computer vision [8]}, load balancing [9]}, biological systems [10]} and text classification [11]}. The authors refer to [12]}, [13]}, [14]} for detailed overviews of various spectral graph clustering algorithms and recent advancements in the field.
