Dynamic Graph Clustering Using Minimum-Cut Trees
Vol. 16, no. 2, pp. 411-446, 2012. Regular paper.
Abstract Algorithms or target functions for graph clustering rarely admit quality guarantees or optimal results in general. Based on properties of minimum-cut trees, a clustering algorithm by Flake et al. does however yield such a provable guarantee, which ensures the quality of bottlenecks within the clustering. We show that the structure of minimum s-t-cuts in a graph allows for an efficient dynamic update of those clusterings, and present a dynamic graph clustering algorithm that maintains a clustering fulfilling this quality guarantee, and that effectively avoids changing the clustering. Experiments on real-world dynamic graphs complement our theoretical results.
Submitted: September 2010.
Accepted: June 2012.
Final: July 2012.
Published: August 2012.
Communicated by Michael Kaufmann
article (PDF)