Roach type of graphs and the characteristics of their partitioning

No Thumbnail Available

Date

2013

Journal Title

Journal ISSN

Volume Title

Publisher

University of Kelaniya

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.

Description

Keywords

Citation

Perera, K.K.K.R., 2013. Roach type of graphs and the characteristics of their partitioning, Proceedings of the Annual Research Symposium 2013, Faculty of Graduate Studies, University of Kelaniya, pp 97.

Collections

Endorsement

Review

Supplemented By

Referenced By