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] 
  • R. Görke, T. Hartmann and D. Wagner. "Dynamic Graph Clustering Using Minimum-Cut Trees". 2011. [More] 
  • R. Görke, A. Meyer-Bäse, C. G. Wagner, H. He, M. R. Emmett and C. A. Conrad. "Determining and interpreting correlations in lipidomic networks found in glioblastoma cells", BMC Systems Biology, Vol. 4, September, 2010. [More] 
  • O. F. Lafou. "Engineering von Modularity-basiertem Graphenclustern,". 2010. [More] 
  • R. Görke, P. Maillard, C. Staudt and D. Wagner. "Modularity-Driven Clustering of Dynamic Graphs". Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). P. Festa ed. 2010. pp. 436-448. [More] 
  • A. Meyer-Bäse, R. Görke, H. He, M. R. Emmett, A. G. Marshall and C. A. Conrad. "Computational techniques to the topology and dynamics of lipidomic networks found in glioblastoma cells". Proceedings of SPIE 7704: Evolutionary and Bio-Inspired Computation: Theory and Applications IV (2010). 2010. [More] 
  • C. Staudt. "Experimental Evaluation of Dynamic Graph Clustering Algorithms". 2010. [More] 
  • R. Görke. "An Algorithmic Walk from Static to Dynamic Graph Clustering". Department of Informatics. 2010. [More] 
  • R. Görke, M. Gaertler, F. Hübner and D. Wagner. "Computational Aspects of Lucidity-Driven Graph Clustering", Journal of Graph Algorithms and Applications, Vol. 14, January, 2010, pp. 165-197. [More] 
  • M. Holzer, F. Schulz, D. Wagner, G. Prasinos and C. Zaroliagis. "Engineering planar separator algorithms", ACM Journal of Experimental Algorithmics, Vol. 14, December, 2009, pp. 1-31. [More] 
  • R. Görke, T. Hartmann and D. Wagner. "Dynamic Graph Clustering Using Minimum-Cut Trees". Algorithms and Data Structures, 11th International Workshop (WADS'09). F. Dehne, J.-R. Sack and R. Tamassia eds. 2009. pp. 339-350. [More] 
  • D. Delling, R. Görke, C. Schulz and D. Wagner. "ORCA Reduction and ContrAction Graph Clustering". Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM'09). A. V. Goldberg and Y. Zhou eds. 2009. pp. 152-165. [More] 
  • S. Mukhtar. "Dynamische Clusteranalyse für DM-Verkaufsdaten". Department of Informatics. 2009. [More] 
  • R. Görke and C. Staudt. "A Generator for Dynamic Clustered Random Graphs". ITI Wagner, Department of Informatics, Universität Karlsruhe. 2009. [More] 
  • S. Nagel. "Optimisation of Clustering Algorithms for the Identification of Customer Profiles from Shopping Cart Data". Department of Informatics. 2008. [More] 
  • T. Hartmann. "Clustering Dynamic Graphs with Guaranteed Quality". Department of Informatics. 2008. [More] 
  • D. Delling, M. Gaertler, R. Görke and D. Wagner. "Engineering Comparators for Graph Clusterings". Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM'08). 2008. pp. 131-142. [More] 
  • C. Schulz. "Design and Experimental Evaluation of a Local Graph Clustering Algorithm". 2008. [More] 
  • M. Holzer. "Engineering Planar-Separator and Shortest-Path Algorithms". Department of Informatics. 2008. [More] 
  • F. Hübner. "The Dynamic Graph Clustering Problem - ILP-Based Approaches Balancing Optimality and the Mental Map". Department of Informatics. 2008. [More] 
  • M. Krings. "LP-basierte Heuristiken für Graphenclusterung mit Modularity als Qualitätsmaß". 2008. [More] 
  • D. Glaser. "Zeitexpandiertes Graphenclustern - Modellierung und Experimente". Department of Informatics. 2008. [More] 
  • U. Brandes et al. "On Modularity Clustering", IEEE Transactions on Knowledge and Data Engineering, Vol. 20, February, 2008, pp. 172-188. [More] 
  • U. Brandes et al.. "On Finding Graph Clusterings with Maximum Modularity". Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07). A. Br, Städt, D. Kratsch and H. Müller eds. 2007. pp. 121-132. [More] 
  • D. Delling, M. Gaertler, R. Görke, Z. Nikoloski and D. Wagner. "Engineering the evaluation of clustering techniques". Proceedings of the European Conference of Complex Systems (ECCS'07). 2007. [More] 
  • M. Gaertler, R. Görke and D. Wagner. "Significance-Driven Graph Clustering". Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM'07). 2007. pp. 11-26. [More] 
  • S. Lang. "Protein domain decomposition using spectral graph partitioning". 2007. [More] 
  • M. Freidinger. "Minimale Schnitte und Schnittbäume". 2007. [More] 
  • S. Wagner and D. Wagner. "Comparing Clusterings -- An Overview". Universität Karlsruhe (TH). Tech. Rep. 2006-04. 2007. [More] 
View less
  

Projects

[ Back ]