Dynamic Graph Clustering Using Minimum-Cut Trees
| Autor: | Robert Görke, Dorothea Wagner, Tanja Hartmann |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
General Computer Science
Computer science Single-linkage clustering Correlation clustering Strength of a graph Tree (graph theory) Computer Science Applications Theoretical Computer Science Computational Theory and Mathematics Minimum cut Geometry and Topology Cluster analysis Algorithm Complement (set theory) Clustering coefficient |
| Zdroj: | Journal of Graph Algorithms and Applications. 16:411-446 |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00269 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|