id: 06112213
dt: j
an: 06112213
au: Görke, Robert; Hartmann, Tanja; Wagner, Dorothea
ti: Dynamic graph clustering using minimum-cut trees.
so: J. Graph Algorithms Appl. 16, No. 2, 411-446 (2012).
py: 2012
pu: Brown University, Providence, RI; University of Texas, Dallas, TX
la: EN
cc: 
ut: clustering algorithm
ci: 
li: doi:10.7155/jgaa.00269
ab: 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.
rv: