Arbeitsvorhaben Prof. Dr. Gerhard Reinelt

Netzwerke - Analyse und Optimierung

Viele interessante und relevante Phänomene in Sozial- und Naturwissenschaften und in der Ökonomie können durch Graphen bzw. Netzwerke modelliert werden. Als besonders relevant haben sich dabei in jüngster Zeit solche Netzwerke erwiesen, die einerseits Millionen von Knoten und andererseits eine große zeitliche Dynamik aufweisen. Gerade diese Eigenschaften sind aber bisher von der algorithmischen Forschung nicht hinreichend gewürdigt (große Netzwerke) bzw. sogar vernachlässigt worden (dynamische Netze). Im Rahmen der Fellowship möchte ich einerseits mit meiner algorithmischen Forschung dazu beitragen, genau diese methodische Lücke zu schließen, und andererseits gemeinsam mit Heidelberger Wissenschaftlern, die in ihren Gebieten solchen Netzwerken begegnen, Fortschritte auf deren Arbeitsgebieten ermöglichen.

Beispiele für das breite Anwendungsspektrum von Netzen in unterschiedlichen Gebieten (zu denen ich teilweise auch schon Kontakt hatte) sind etwa:

• Netze in den Sozialwissenschaften zur Modellierung z.B. von Dominanzen, Interaktionen oder Konflikten,
• Erfassung von Wirkungen zwischen den relevanten Wirtschaftssektoren, in die die Volkswirtschaft eines Landes eingeteilt werden kann,
• allgemeine Verbindungsnetze in der Logistik, wie z.B. Straßennetze oder Fahrpläne,
• Energienetze, bei denen Fragen der Stabilität und Zuverlässigkeit auch unter unvorhergesehenen Einwirkungen von außen von großer Bedeutung sind,
• regulatorische Gen-Netzwerke und Signalpfade in der Systembiologie,
• Small-World-Phänomene, d.h. kurze Interaktionswege, obwohl die zugrundeliegenden Netze extrem groß sind,
• Kommunikationsnetzwerke wie im World-Wide-Web zahlreich vertreten, für die das Studium vieler Phänomene wie Verbreitungsgeschwindigkeit von Nachrichten, Wichtigkeit von Knoten, etc. wünschenswert wäre.

Mein Arbeitsgebiet ist die Diskrete und Kombinatorische Optimierung. Netzwerke spielen hier nicht nur aus theoretischer Sicht eine wichtige Rolle, sondern auch dadurch, dass die Behandlung vieler Anwendungen zu Optimierungsproblemen für Netzwerkmodelle führen. Die Lösung von Optimierungsproblemen wie Kürzeste-Wege-Berechnung oder Minimaler-Schnitt-Bestimmung auf statischen
Netzwerken moderater Größenordnungen ist recht gut verstanden und es gibt leistungsfähige Algorithmen. Bei den Netzwerken allerdings, die in diesem Vorhaben betrachtet werden sollen, kommen einige neue Aspekte und Fragestellungen hinzu:

• Welche Eigenschaften dieser Netzwerke sind für die jeweiligen Wissenschaften interessant?
• Können diese Eigenschaften auch tatsächlich berechnet oder geschätzt werden? Hier stellt sich insbesondere die Frage nach den Leistungsgrenzen schneller Algorithmen für sehr große Netzwerke. Bei Vorliegen von Millionen Knoten kann u.U. bereits eine sonst als vorteilhaft geltende Laufzeit, die nur quadratisch mit der Problemgröße wächst, nicht mehr akzeptabel sein.
• Bei dynamischen, zeitlich veränderlichen Netzwerken ist zu erforschen, ob eine Reoptimierung mit wenig Aufwand möglich ist.
• Ein möglicher Ansatz bei großen Netzwerken wäre, die gewünschte Optimierung nur approximativ durchzuführen. Es ist dann erforschen, ob für geeignete Algorithmen eine Gütegarantie für die Qualität der gefundenen Lösung gegeben werden kann oder ob vielleicht das Netzwerk gar nicht komplett betrachtet werden muss.

Ich möchte das Jahr im Marsilius-Kolleg dazu verwenden, tiefer in dieses aktuelle und neue Forschungsgebiet einzudringen. Die mathematischen und informatischen Grundlagen zur Behandlung von sehr großen und dynamischen Netzwerken sollen weiterentwickelt werden und in der Zusammenarbeit mit Kollegen sollen neue Modellierungsmöglichkeiten für die Wissenschaften
aufgezeigt bzw. die Behandlung vorhandener Modelle erst ermöglicht werden. Die dazu erforderliche algorithmische Kompetenz ist in der Heidelberger Informatik und am IWR vertreten. Was noch fehlt ist die Bündelung dieser Kompetenz hin auf dieses neue wichtige Gebiet, sowie das intensive Gespräch mit Forschern aus den Sozial- und Lebenswissenschaften, um eine gemeinsame Sprache zu entwickeln und die dort auftretenden Probleme in geeigneter Weise zu formalisieren und zu lösen. Dabei sollen insbesondere solche
Anwendungsgebiete und Themen identifiziert werden, die Chancen auch für längerfristige interdisziplinäre Forschungsprojekte bieten. Die enge Zusammenarbeit mit den Kollegen Glückler und Hamprecht bietet meiner Meinung nach eine ideale Voraussetzung zur erfolgreichen Durchführung dieses Forschungsvorhabens. Hinzu kommt die Expertise von Frau Zweig mit Schwerpunkten im Bereich von Zentralitätsindizes und Clustering-Algorithmen, die für viele Anwendungen in Biologie, Wirtschaft, Chemie und  Sozialwissenschaften benötigt
werden.