Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Modellierung und Analyse komplexer Systeme

Forschung / Research

Forschungsschwerpunkte 


Die Arbeitsgruppe 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 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 Teil unserer Forschungsergebnisse sind auch auf unserem Youtube-Kanal einsehbar.

 

Algorithmische Netzwerkanalyse

Dieser Bereich befasst sich mit der strukturellen Untersuchung komplexer Netzwerke und wird momentan durch das DFG SPP Algorithms for Big Data gefördert. 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.

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 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: