Browsing by Author "WIJAYA, Derry Tanti"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Ricochet: A Family of Unconstrained Algorithms for Graph clustering
    (2007-07-30) WIJAYA, Derry Tanti; BRESSAN, Stephane
    Partitional graph clustering algorithms like K-means and Star necessitate a priori decisions on the number of clusters and threshold on the weight of edges to be considered, respectively. These decisions are difficult to make and their impact on clustering performance can be 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 on 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. In particular, we evaluate the impact of removing the constraints on the number of clusters and threshold by comparing the performance of our algorithms with K-means and Star. We are also comparing the performance of our algorithms with Markov Clustering which is not parameterized by number of clusters nor threshold but has a fine tuning parameter that impacts the coarseness of the result clusters.