Regularity-based spectral clustering and mapping the Fiedler-carpet

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.

Keywords

• multiway discrepancy
• correspondence analysis
• normalized laplacian
• multiway cuts
• fiedler-vector
• weighted k-means algorithm
• 05c50
• 62h25
• 65h10