Abstract:
The goal of the graph partitioning problem is to find groups such that entities within the same group are similar and different groups are dissimilar. Spectral clustering methods use eigenvalues and eigenvectors of matrices associated with graphs and are widely used in graph-partitioning problems.
In this presentation, results concerning spectral clustering properties of roach type of graphs
(
and
are the number of vertices in the upper and lower paths of the graph) will be presented. The concrete formula for the minimum normalized cut of
has already been presented, (Perera & Mizoguchi, 2013). The normalized cut is used to minimize the disassociation between partitions of graphs and maximize the association within partitions. Here we find the characteristic polynomials for the normalized Laplacian matrix of weighted path
and roach type of graphs
using Chebyshev polynomials and properties of tridiagonal matrices. Subsequently, we find conditions for
and
, based on which spectral methods perform poorly compared with the minimum normalized cut.
