151. Regularity-based spectral clustering and mapping the Fiedler-carpet
- Author
-
Bolla Marianna, Winstein Vilas, You Tao, Seidl Frank, and Abdelkhalek Fatma
- Subjects
multiway discrepancy ,correspondence analysis ,normalized laplacian ,multiway cuts ,fiedler-vector ,weighted k-means algorithm ,05c50 ,62h25 ,65h10 ,Mathematics ,QA1-939 - Abstract
We discuss spectral clustering from a variety of perspectives that include extending techniques to rectangular arrays, considering the problem of discrepancy minimization, and applying the methods to directed graphs. Near-optimal clusters can be obtained by singular value decomposition together with the weighted kk-means algorithm. In the case of rectangular arrays, this means enhancing the method of correspondence analysis with clustering, while in the case of edge-weighted graphs, a normalized Laplacian-based clustering. In the latter case, it is proved that a spectral gap between the (k−1)\left(k-1)st and kkth smallest positive eigenvalues of the normalized Laplacian matrix gives rise to a sudden decrease of the inner cluster variances when the number of clusters of the vertex representatives is 2k−1{2}^{k-1}, but only the first k−1k-1 eigenvectors are used in the representation. The ensemble of these eigenvectors constitute the so-called Fiedler-carpet.
- Published
- 2022
- Full Text
- View/download PDF