Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-00887-0_13
Title: Ricochet: A family of unconstrained algorithms for graph clustering
Authors: Wijaya, D.T.
Bressan, S. 
Keywords: Clustering
Document clustering
Kmeans clustering
Star clustering
Weighted graph clustering
Issue Date: 2009
Source: Wijaya, D.T.,Bressan, S. (2009). Ricochet: A family of unconstrained algorithms for graph clustering. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5463 : 153-167. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-00887-0_13
Abstract: Partitional graph clustering algorithms like K-means and Star necessitate a priori decisions on the number of clusters and threshold for the weight of edges to be considered, respectively. These decisions are difficult to make and their impact on clustering performance is significant. We propose a family of algorithms for weighted graph clustering that neither requires a predefined number of clusters, unlike K-means, nor a threshold for the weight of edges, unlike Star. To do so, we use re-assignment of vertices as a halting criterion, as in K-means, and a metric for selecting clusters' seeds, as in Star. Pictorially, the algorithms' strategy resembles the rippling of stones thrown in a pond, thus the name 'Ricochet'. We evaluate the performance of our proposed algorithms using standard datasets and evaluate the impact of removing constraints by comparing the performance of our algorithms with constrained algorithms: K-means and Star and unconstrained algorithm: Markov clustering.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40955
ISBN: 9783642008863
ISSN: 03029743
DOI: 10.1007/978-3-642-00887-0_13
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 5, 2017

Page view(s)

58
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.