Author(s)： K. K. K. R. Perera and Yoshihiro Mizoguchi

J. Math-for-Ind. 5A (2013) 59-72.

• File： JMI2013A-8.pdf (259KB)

Abstract
The main objective of this paper is to solve the problem of finding graphs on which the spectral clustering method and the normalized cut produce different partitions. To this end, we derive formulae for minimum normalized cut for graphs in some classes such as paths, cycles, complete graphs, double-trees, lollipop graphs $LP_{n,m}$, roach type graphs $R_{n,k}$ and weighted paths $P_{n,k}$.

Keyword(s).　 spectral clustering, normalized Laplacian matrices, difference Laplacian matrices, signless Laplacian matrices, normalized cut