06112213

j

06112213 G\"orke, Robert Hartmann, Tanja Wagner, Dorothea Dynamic graph clustering using minimum-cut trees. J. Graph Algorithms Appl. 16, No. 2, 411-446 (2012). 2012 Brown University, Providence, RI; University of Texas, Dallas, TX EN clustering algorithm

doi:10.7155/jgaa.00269

Summary: 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 {\it G. W. Flake}, {\it R. E. Tarjan} and {\it K. Tsioutsiouliklis} [Internet Math. 1, No. 4, 38--408 (2004; Zbl 1098.68095)] 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.