Clustering of Static and Temporal Graphs
Project Members
Funding
Subproject of the Priority Programme 1307 Algorithm Engineering of the Deutsche Forschungsgemeinschaft (German Research Foundation).
Summary
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.