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:
- H. Meyerhenke, P. Sanders, C. Schulz: Parallel Graph Partitioning for Complex Networks. In IEEE Trans. Parallel Distrib. Syst. 28: 2625-2638 (2017).
[arXiv preprint] [DOI: 10.1109/TPDS.2017.2671868] (c) IEEE - H. Meyerhenke, T. Sauerwald: Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning. Algorithmica 64(3):329-361, November 2012. Special issue on ISAAC'10.
[abstract] [bibtex] [preprint (pdf)] [DOI:10.1007/s00453-012-9666-y] - H. Meyerhenke, B. Monien, T. Sauerwald: A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions. Journal of Parallel and Distributed Computing, 69(9):750-761, 2009. Best Paper Awards and Panel Summary: 22nd International Parallel and Distributed Processing Symposium (IPDPS 2008). [abstract] [bibtex] [preprint (pdf)] [DOI: 10.1016/j.jpdc.2009.04.005]
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:
- M. Wegner, O. Taubert, A. Schug, H. Meyerhenke: Maxent-stress Optimization of 3D Biomolecular Models. In Proc. 25th European Symposium on Algorithms (ESA 2017).
[arXiv preprint] - H. Meyerhenke, M. Nöllenburg, C. Schulz: Drawing Large Graphs by Multilevel Maxent-Stress Optimization. In IEEE Trans. Vis. Comput. Graph. 24(5): 1814-1827 (2018).
[arXiv preprint] [DOI: 10.1109/TVCG.2017.2689016] - X. Liu, P. R. Pande, H. Meyerhenke, D.A. Bader: PASQUAL: Parallel Techniques for Next Generation Genome Sequence Assembly. IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 5, pp. 977-986, May 2013.
[abstract] [bibtex] [preprint (pdf)] [supplementary material (pdf)] [DOI: 10.1109/TPDS.2012.190]