Forschung

Achtung: Webseiten noch im Aufbau

Forschungsschwerpunkte 

Die Forschungsgruppe unter der Leitung von Prof. Dr. Henning Meyerhenke beschäftigt sich mit Fragestellungen aus der parallelen/verteilten Algorithmentechnik. Wir entwickeln, analysieren und implementieren praxistaugliche und theoretisch fundierte skalierbare diskrete Algorithmen für große und komplexe vernetzte Systeme. Von besonderer Bedeutung sind dabei Graphenalgorithmen.

Unsere aktuellen Schwerpunkte liegen in folgenden Bereichen:

  • Algorithmische Analyse von großen komplexen Netzwerken, insbesondere unter Berücksichtigung dynamischer Änderungen

  • Kombinatorisches wissenschaftliches Rechnen, insbesondere Graphpartitionierung und Lastbalancierung sowie Scheduling

  • Angewandte Optimierung, insbesondere für algorithmisch schwierige Probleme aus den Naturwissenschaften

Ein (sehr kleiner) Teil unserer Forschungsergebnisse sind auch auf unserem Youtube-Kanal einsehbar, der während der Zugehörigkeit zur HU Berlin entstanden ist. Die ausgewählten Veröffentlichungen unten werden noch im Rahmen des Neuaufbaus unserer KIT-Webseiten aktualisiert.

 

Algorithmische Netzwerkanalyse

Dieser Bereich befasst sich mit der strukturellen Untersuchung komplexer Netzwerke und wurde über die Jahre durch verschiedene Drittmittelprojekte der DFG und des MWK Baden-Württemberg unterstützt. Komplexe Netzwerke haben sich in vielen Bereichen der Wissenschaft als Modellierungswerkzeug bewährt. Ihre statistische Analyse mit mathematischen und angewandten algorithmischen Methoden liefert tiefere Einsichten über den strukturellen Zusammenhang der modellierten Entitäten und ihrer Verbindungen. Beispielsweise können durch unsere Algorithmen wichtige Personen in einem sozialen Netzwerk identifiziert oder die natürliche Gruppenstruktur des Netzwerks erkennbar gemacht werden. Die Implementierungen unserer Algorithmen werden in der Software NetworKit gebündelt, die unter unserer Federführung quelloffen entwickelt und international eingesetzt wird (> 300 Repositorien auf github nutzten Anfang 2025 NetworKit).

Ausgewählte Veröffentlichungen:
  • E. Bergamini, P. Crescenzi, G. D'Angelo, H. Meyerhenke, L. Severini, Y. Velaj: Improving the Betweenness Centrality of a Node by Adding Links. In ACM Journal of Experimental Algorithmics 23 (2018).
    [DOI: 10.1145/3166071]
  • E. Bergamini, H. Meyerhenke: Approximating Betweenness Centrality in Fully-dynamic Networks. In Internet Mathematics 12(5): 281-314 (2016). Taylor and Francis Group.
    [arXiv preprint] [DOI: 10.1080/15427951.2016.1177802]
  • C.L. Staudt, A. Sazonovs, H. Meyerhenke: NetworKit: A Tool Suite for Large-scale Network Analysis. In Network Science 4(4), pp. 508–530, December 2016. Cambridge University Press.
    [preliminary version at arXiv] [DOI: 10.1017/nws.2016.20]
  • C.L. Staudt, H. Meyerhenke: Engineering Parallel Algorithms for Community Detection in Massive Networks. IEEE Transactions on Parallel and Distributed Systems vol. 27, no. 1, pp. 171-184, 2016. Extended and updated version of ICPP'13 paper.
    [arXiv preprint] [DOI: 10.1109/TPDS.2015.2390633] (c) 2015 IEEE

 

Kombinatorisches wissenschaftliches Rechnen

Dieser Bereich entwickelt theoretische Grundlagen, kombinatorische Algorithmen und Tools, die zur Verbesserung paralleler Methoden des wissenschaftlichen Rechnens beitragen. Hier ist insbesondere die Lastbalancierung von parallelen Graphen- und Matrixalgorithmen zu nennen, wie sie etwa in numerischen Simulationen verwendet werden. Im Rahmen des DFG-Projekts TEAM und des BMBF-Projekts WAVE entwickelten wir Methoden, die solche und ähnliche Simulationen derartig auf Parallelrechner abbilden, dass jeder Prozessor gleich viel Arbeitslast hat und möglichst wenig mit anderen Prozessoren kommunizieren muss. In diesem Zusammenhang betrachten wir auch anwendungsnahe Scheduling-Verfahren.

Ausgewählte Veröffentlichungen:

 

Angewandte kombinatorische Optimierung

Dieser (vglw. kleine) Bereich beschäftigt sich mit beweisbar schwierigen algorithmischen Problemstellungen, die oft durch naturwissenschaftliche Anwendungen motiviert sind. Hier wollen wir durch innovative und in der Regel parallele Algorithmen größere Probleminstanzen in kürzerer Zeit lösen und so neue Fortschritte in den Anwendungswissenschaften ermöglichen.

Ausgewählte Veröffentlichungen: