[boost] Interest in Graph Clustering Algorithms

From: Eric Breimer (ebreimer_at_[hidden])
Date: 2005-07-20 08:52:24

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.