A clustering algorithm based on graph connectivity

Authors
Hartuv, E Shamir, R
Citation
E. Hartuv et R. Shamir, A clustering algorithm based on graph connectivity, INF PROCESS, 76(4-6), 2000, pp. 175-181
Citations number
22
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
76
Issue
4-6
Year of publication
2000
Pages
175 - 181
Database
ISI
SICI code
0020-0190(200012)76:4-6<175:ACABOG>2.0.ZU;2-Q
Abstract
We have developed a novel algorithm for cluster analysis that is based on g raph theoretic techniques. A similarity graph is defined and clusters in th at graph correspond to highly connected subgraphs. A polynomial algorithm t o compute them efficiently is presented. Our algorithm produces a solution with some provably good properties and performs well on simulated and real data. (C) 2000 Elsevier Science B.V. All rights reserved.