Geodesic
Dynamic Graph Clustering Using Minimum-Cut Trees
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 411-446.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00269
Keywords: Dynamic Graphs, Cut Trees, Graph Clustering, Networkanalysis 
@article{JGAA_2012_16_2_a11,
     author = {Robert G\"orke and Tanja Hartmann and Dorothea Wagner},
     title = {Dynamic {Graph} {Clustering} {Using} {Minimum-Cut} {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {411--446},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00269},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00269/}
}
TY  - JOUR
AU  - Robert Görke
AU  - Tanja Hartmann
AU  - Dorothea Wagner
TI  - Dynamic Graph Clustering Using Minimum-Cut Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 411
EP  - 446
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00269/
DO  - 10.7155/jgaa.00269
LA  - en
ID  - JGAA_2012_16_2_a11
ER  - 
%0 Journal Article
%A Robert Görke
%A Tanja Hartmann
%A Dorothea Wagner
%T Dynamic Graph Clustering Using Minimum-Cut Trees
%J Journal of Graph Algorithms and Applications
%D 2012
%P 411-446
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00269/
%R 10.7155/jgaa.00269
%G en
%F JGAA_2012_16_2_a11
Robert Görke; Tanja Hartmann; Dorothea Wagner. Dynamic Graph Clustering Using Minimum-Cut Trees. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 411-446. doi : 10.7155/jgaa.00269. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00269/

Cité par Sources :