Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871235 | Discrete Applied Mathematics | 2018 | 4 Pages |
Abstract
In this short note we strengthen a former result of Bolla (2011), where in a multipartition (clustering) of a graph's vertices we estimated the pairwise discrepancies of the clusters with the normalized adjacency spectra. There we used the definition of Alon et al. (2010) for the volume-regularity of the cluster pairs. Since then, in Bolla (2016) we defined the so-called k-way discrepancy of a k-clustering and estimated the kth largest (in absolute value) normalized adjacency eigenvalue with an increasing function of it. In the present paper, we estimate the new discrepancy measure with this eigenvalue. Putting these together, we are able to establish a relation between the large spectral gap (as for the (kâ1)th and kth non-trivial normalized adjacency eigenvalues) and the sudden decrease between the kâ1 and k-way discrepancies. It makes rise to a new paradigm of spectral clustering, which minimizes the multiway discrepancy.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marianna Bolla, Ahmed Elbanna,