Graph clustering and minimum cut trees

Gary William Flake, Robert E. Tarjan, Kostas Tsioutsiouliklis

Research output: Contribution to journalArticle

211 Scopus citations

Abstract

In this paper, we introduce simple graph clustering methods based on minimum cuts within the graph. The clustering methods are general enough to apply to any kind of graph but are well suited for graphs where the link structure implies a notion of reference, similarity, or endorsement, such as web and citation graphs. We show that the quality of the produced clusters is bounded by strong minimum cut and expansion criteria. We also develop a framework for hierarchical clustering and present applications to real-world data. We conclude that the clustering algorithms satisfy strong theoretical criteria and perform well in practice.

Original languageEnglish (US)
Pages (from-to)385-408
Number of pages24
JournalInternet Mathematics
Volume1
Issue number4
DOIs
StatePublished - 2004

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Graph clustering and minimum cut trees'. Together they form a unique fingerprint.

Cite this