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. We show that the structure of minimum-s-t-cuts in a graph allows for an efficient dynamic update of minimum-cut trees, and present a dynamic graph clustering algorithm that maintains a clustering fulfilling this quality quarantee, and that effectively avoids changing the clustering. Experiments on real-world dynamic graphs complement our theoretical results.
展开▼
