A survey on graph partitioning approach to spectral clustering

Authors

  • Subhanshu Goyal Department of Applied Mathematics & Humanities, S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA
  • M A ZAVERI S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA
  • SUSHIL KUMAR S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA
  • A K SHUKLA S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

DOI:

https://doi.org/10.15625/1813-9663/31/1/4108

Keywords:

Eigenvectors, graph cut, Laplacian matrix, normalized cut, spectral clustering

Abstract

Cluster analysis is an unsupervised technique of grouping  related objects without considering their label or class. The objects  belonging to the same cluster are relatively more  homogeneous in comparison with other clusters. The application of cluster analysis is in areas like gene expression analysis, galaxy formation, natural language processing and image segmentation etc. The clustering problem can be formulated as a graph cut problem where a suitable objective function has to be optimized. This study uses different graph cluster formulations based on graph cut and partitioning problems. A special class of graph clustering algorithm known as spectral clustering algorithms is used for the study. Two widely used spectral clustering algorithms are applied to explaining solution to these problems. These algorithms are generally based on the Eigen-decomposition of  Laplacian matrices of either weighted or non-weighted graphs.

 

Metrics

Metrics Loading ...

Author Biographies

Subhanshu Goyal, Department of Applied Mathematics & Humanities, S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

Research Scholar

Department of Applied Mathematics & Humanities,

S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

M A ZAVERI, S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

Department of Computer Science & Engineering

SUSHIL KUMAR, S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

Department of Applied Mathematics & Humanities

A K SHUKLA, S. V. National Institute of Technology, Surat, Gujarat 395007, INDIA

Department of Applied Mathematics & Humanities

Downloads

Published

2015-03-16

How to Cite

[1]
S. Goyal, M. A. ZAVERI, S. KUMAR, and A. K. SHUKLA, “A survey on graph partitioning approach to spectral clustering”, JCC, vol. 31, no. 1, pp. 31–42, Mar. 2015.

Issue

Section

Computer Science