2008-05: Coring Method for Clustering a Graph

DIMACS TR: 2008-05

Coring Method for Clustering a Graph

Authors: Thang Le, Casimir Kulikowski and Ilya Muchnik

ABSTRACT
Graph clustering partitions a graph into subgraphs with strongly interconnected nodes, while nodes belonging to different subgraphs are weakly connected. In this paper, we propose a new clustering method applicable to either weighted or unweighted graphs in which each cluster consists of a densely connected core region surrounded by a region with lower density. We have developed a highly efficient and robust method to identify nodes belonging to dense cores of clusters. The set of the nodes is then divided into groups, each of which is the representative for one cluster. These groups are finally expanded into complete clusters covering all the nodes of the graph. Experiments with both synthetic and real datasets for gene expression analysis and image segmentation yield very encouraging results.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-05.pdf

DIMACS Home Page