Prof. Dr. Henning Meyerhenke

Prof. Meyerhenke erforscht die effiziente Verarbeitung und Analyse großer Netzwerk-Datenmengen auf verteilten Computersystemen. Sein aktueller Fokus liegt auf dem intelligenten Scheduling von Datenanalyseworkflows auf heterogenen Infrastrukturen sowie auf schnellen numerischen Lösungsverfahren für komplexe Netzwerkprobleme — insbesondere unter Berücksichtigung von Energieeffizienz und CO₂-Reduktion. Für Unternehmen und öffentliche Einrichtungen bedeutet das: Datenanalyse-Pipelines laufen schneller, kostengünstiger und umweltschonender, ohne dabei an Genauigkeit zu verlieren. Die Methoden sind relevant für Branchen, die mit großen Graphen und Netzwerkdaten arbeiten — von Telekommunikation über Logistik bis zu wissenschaftlichen Datenanalysen.

🔒 Das System hat 354 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden

• Schnelle inexakte kombinatorische und algebraische Löser für große Netzwerke

  Quelle ↗

  Zahlreiche bahnbrechende Technologien generieren Datensätze von enormer Größe. Viele dieser Datensätze lassen sich als Netzwerk modellieren. Die so produzierten Datensätze enthalten wertvolle Informationen, die durch geeignete Algorithmen und Software-Tools zur Analyse extrahiert und weiterverarbeitet werden können. In diesem Folgeantrag (zweite Förderphase) fokussieren wir auf die Verbindung von Distanzen in Netzwerken (inkl. Nichtstandard-Distanzmaßen) mit essentiellen Themen der algorithmischen Netzwerkanalyse: (i) Zentralitätsmaße, einschließlich ihrer (ii) Verallgemeinerung zu Gruppenzentralitäten, (iii) Einflussmaximierung und (iv) Netzwerkhyperbolizität. Zentralitätsmaße geben die Wichtigkeit von Knoten oder Kanten an; wir betrachten Maße, die Knoten gemäß ihres durchschnittlichen Abstands zu anderen Knoten ordnen. Gruppenzentralität zielt wiederum auf die Identifizierung einer Menge von Knoten ab, so dass die Distanz zwischen jedem Knoten und mindestens einem aus der Menge klein ist. Bei der Ausbreitung von Einfluss lässt sich die Wahrscheinlichkeit, dass Einfluss propagiert werden kann, auch als eine Art Distanz auffassen. Schließlich gibt die Eigenschaft der Hyperbolizität an, wie ähnlich der metrische Raum eines Graphen zu dem eines Baumes ist. All diese algorithmischen Aufgaben haben zahlreiche Big-Data-Anwendungen. Dazu gehören unter anderem Marketing-Strategien, Routing und Netzwerksicherheit. Trotzdem haben bisherige Algorithmen deutliche Schwächen, wenn die Eingabe groß ist oder eine komplexe Struktur aufweist. Da viele Realwelt-Datensätze bereits Ungenauigkeiten enthalten, befürworten wir einen inexakten Lösungsprozess mit Approximationsalgorithmen und Heuristiken. Wir werden daher für die genannten Aufgaben deutlich verbesserte Algorithmen für den Einsatz in großen und dynamischen Netzwerken entwickeln und implementieren. Die Eingabegröße, die in akzeptabler Zeit handhabbar ist, soll dabei um mindestens eine Größenordnung im Vergleich zum Stand der Technik verbessert werden. Wir integrieren unsere neuen Methoden in die Open-Source-Software zur Netzwerkanalyse NetworKit, welche wann immer möglich Parallelität mit gemeinsamem Speicher nutzt. Das Werkzeug ist frei und kostenlos für die Allgemeinheit und andere SPP-Projekte zugänglich. Dadurch wird die sofortige Anwendung unserer Beiträge auf Realwelt-Probleme, die skalierbare Codes erfordern, gefördert.

• More Recent Advances in (Hyper)Graph Partitioning

  2022

  ACM Computing Surveys · DOI

  In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the past decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic [ 29 ]. In particular, the survey extends the previous survey by also covering hypergraph partitioning and has an additional focus on parallel algorithms.

• Computing top- <i>k</i> Closeness Centrality Faster in Unweighted Graphs

  2019

  ACM Transactions on Knowledge Discovery from Data · DOI

  Given a connected graph G =( V , E ), where V denotes the set of nodes and E the set of edges of the graph, the length (that is, the number of edges) of the shortest path between two nodes v and w is denoted by d ( v , w ). The closeness centrality of a vertex v is then defined as n =1/Σ w ∈ V d ( v , w ), where n =| V |. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the k most central vertices has been deeply analyzed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the article, we prove that it is not solvable in time O (| E | 2=ϵ ) on directed graphs, for any constant ϵ &gt; 0, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the k most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top k nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the 10 most central actors in the Internet Movie Database (IMDB) collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page p to a page q if p contains a link to q .