Interest in Graph Clustering Algorithms

We are interested in submitting a collection of novel graph clustering algorithms to the Boost Graph Library and we wanted to see if there was any interest. Unlike conventional clustering algorithms that partition a graph into disjoint subsets, our algorithms efficiently compute locally optimal dense subsets. This can lead to overlapping clusters, which has advantages in many applications. The algorithms have been shown to work effectively on both synthetic and real-world graphs, and also have been shown to outperform well-known k-neighborhood heuristics. See: 1. http://www.cs.rpi.edu/~goldberg/publications/isi-05-clust.pdf 2. http://www.cs.rpi.edu/~goldberg/publications/iadis-clus.doc The algorithms are truly general-purpose. They work on any type of graph; A user only needs to supply a density metric. A density metric can factor the size of the cluster to help control or regulate the size of the desired clusters. We have efficient algorithms for creating an initial set of clusters based on a given density metric, and we have efficient algorithms that can refine and optimize the density of an existing set of clusters.
participants (1)
-
Eric Breimer