Algorithm Engineering for Graph Clustering

                                 Dorothea Wagner

           Karlsruher Institut für Technologie (KIT), Karlsruhe, Germany
                             dorothea.wagner@kit.edu

    Graph clustering has become a central tool for the analysis of networks in
general, with manifold applications e.g. in data mining, social networks, biology
or complex systems. The general aim of graph clustering is to identify dense
groups in networks. Countless formalizations thereof exist, among those the
widespread measure modularity. However, the overwhelming majority of algo-
rithms for graph clustering relies on heuristics, e.g., for some NP-hard optimiza-
tion problem, and do not allow for any structural guarantee on their output.
Moreover, networks in the real world are often large, evolve over time or come
as a data stream.
    The talk will discuss algorithmic aspects of graph clustering, especially qual-
ity measures and algorithms that are based on the intuition of identifying as
clusters dense subgraphs that are loosely connected among one another. We
will focus on the algorithm engineering methodology which consists in a cycle
of design, analysis, implementation, and experimental evaluation of algorithms,
bridging the gap between algorithm theory and practical applications. Special
emphasis will be on clustering large networks.
Biography. Dorothea Wagner is a full professor for Informatics at the Karlsruhe In-
stitute of Technology (KIT). Her research interests include design and analysis of al-
gorithms and algorithm engineering, graph algorithms, computational geometry and
discrete optimization, particularly applied to transportation systems, energy systems,
network analysis, data mining and visualization. Among other activities she is member
of the German Council of Science and Humanities (Wissenschaftsrat. From 2007 to
2014 she was vice president of the DFG (Deutsche Forschungsgemeinschaft - German
Research Foundation) and 2004 to 2013 speaker of the scientific advisory board of
Dagstuhl - Leibniz Center for Informatics. In 2012 she received a Google Focused Re-
search Award, she is member of Academia Europaea and Fellow of the GI (Gesellschaft
fr Informatik). Dorothea Wagner obtained her diploma and Ph.D. degrees from the
RWTH Aachen in 1983 and 1986 respectively; and 1992 the Habilitation degree from
the TU Berlin. 1994 - 2003 she was a full professor at the University of Konstanz.