Clustering of Static and Temporal Graphs

Description

Prof. Dr. Dorothea Wagner; Karlsruhe Institute of Technology

 

Project website

 

As a result of the rapidly growing extent of electronically available data, methods for the localization of relevant information and their intelligent organization are of increasing importance. The field of algorithmics is faced with the challenge of providing efficient and feasible algorithms for data clustering. This does not only encompass the development of algorithms that work well for specific applications or sets of data, but also the systematic design of algorithms for formally and rigorously defined problems and their analysis and evaluation with respect to adequate criteria of quality. In this project algorithms for the clustering of graphs shall be developed.

The focal point of our interest are clusterings which are based on the intuition of identifying as clusters dense subgraphs that are loosely connected among one another. To this end we shall underlay a systematic classification of quality measures, which allows for an unbiased comparison of various methodologies. In particular we will engage in the as yet novel field of clustering evolving or time-dependent graphs. As far as possible, the evaluation of algorithms will be based on theoretical analyses, however, fundamentally it shall be conducted experimentally, namely employing suitably generated graphs on the one hand and taking into account real instances on the other hand. As usual in algorithm engineering, we shall traverse the entire cycle of design, analysis, implementation and experimental assessment, in particular reincorporating the results of experiments in the design and the analysis. Our implementations shall be made available in form of software-tools consisting of algorithms, quality indices, measures and procedures of comparison, graph generators as well as benchmarks.

 

Software Projects

Further software projects can be also found here.

  
  

Publications

  • C. Doll. "Hierarchical Cut Clustering in Dynamic Scenarios". 2011. [More] 
  • R. Görke, P. Maillard, A. Schumm, C. Staudt and D. Wagner. "Dynamic Graph Clustering Combining Modularity and Smoothness". ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT). 2011. [More] 
  • R. Görke, T. Hartmann and D. Wagner. "Dynamic Graph Clustering Using Minimum-Cut Trees". ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT). 2011. [More] 
  • C. Doll, T. Hartmann and D. Wagner. "Fully-Dynamic Hierarchical Graph Clustering Using Cut Trees". ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT). 2011. [More] 
  • R. Görke, P. Maillard, A. Schumm, C. Staudt and D. Wagner. "Dynamic Graph Clustering Combining Modularity and Smoothness". 2011. [More] 
View All
  

Projects

[ Back ]