Algorithmik großer und komplexer Netzwerke

In der heutigen Gesellschaft spielt Vernetzung eine Schlüsselrolle. Informationsverbreitung, Kommunikation, Mobilität und Transport basieren ebenso auf Netzwerken wie das soziale und politische Handeln von Organisationen und Personen. In vielen Forschungsgebieten wird mit Netzwerken gearbeitet bzw. werden Netzwerke untersucht. Die Umsetzung dieser Anstrengungen auf konkrete Probleme wird praktisch immer mit Rechnern realisiert. Der Algorithmik als einer der Grundlagen der Informatik und gleichzeitigem Bindeglied zur Mathematik wird dabei eine Schlüsselrolle zuteil, da sie wie kaum ein anderes Gebiet Querverbindungen zwischen verschiedenen Bereichen herstellt. Fortschritte bei der Entwicklung von algorithmischen Lösungen für Netzwerkprobleme haben Konsequenzen für alle mit Netzwerken befassten Disziplinen; sie sind notwendige Voraussetzung für deren Erfolg.

Um die Abläufe und Funktionsweisen innerhalb von Netzwerken zu beherrschen, müssen wir die dahinterliegenden abstrakten Strukturen verstehen. Dazu gehört die effiziente algorithmische Lösung grundlegender Problemstellungen in Netzwerken ebenso wie deren strukturelle Analyse und geeignete Visualisierung. Die Algorithmik auf Netzwerken bzw. Graphen ist innerhalb der Mathematik und Informatik ein klassisches Thema, dessen Grundlagen bereits gut untersucht sind. Graphenalgorithmen gehören zu den ältesten Verfahren in der Algorithmentheorie. Grundlegende Graphenalgorithmen wie kürzeste-Wege-Algorithmen oder Flussalgorithmen werden in der Praxis angewendet. Jedoch wird das Potential algorithmischer Verfahren bei weitem noch nicht ausgeschöpft. Selbst das Verhalten vieler theoretisch gut analysierter Algorithmen ist für große und komplexe Datenmengen konkrete Anwendungsprobleme bzw. echte Anwendungsdaten kaum erforscht. Angesichts des rasanten Wachstums anwendungsbasierter Netze - man denke nur an Netzwerke im Verkehrsbereich oder das WWW - ist weit mehr als die Adaption bekannter Verfahren erforderlich. An dieser Stelle soll das Schwerpunktprogramm durch eine gezielte Weiterentwicklung anwendungsmotivierter, methodischer Forschung eingreifen.

• Beispiel Bahnverkehr

  Anstehende Probleme bei der Zusammenführung verschiedener Verkehrsmittel und der Bewertung des entsprechenden Beförderungsangebots sind gleichzeitig umfangreich und komplex. Möchte man die Qualität des europäischen Bahnnetzes optimieren, so hat man es mit einem Schienennetz aus 30.000 Netzwerkknoten und 1.000.000 Netzwerkverbindungen zu tun. Die Einbeziehung der zeitlichen Komponente mittels Modellierung jeder Ankunft und Abfahrt eines Zuges als Netzwerkknoten lässt bereits für einen Verkehrstag die Knotenzahl um einen Faktor von etwa 150 anwachsen. Ausbaumaßnahmen großen Umfangs können in diesem Netz nicht mehr vorgenommen werden. Optimierung muss durch einzelne netzwirksame Maßnahmen erfolgen. Allerdings ist schon die Bewertung der Auswirkung einzelner lokaler Ausbaumaßnahmen oder einzelner zusätzlicher Zugverbindungen auf das gesamte Netz ein hochgradig komplexes Problem. Umso anspruchsvollere Methoden erfordert die Optimierung eines derart riesigen Netzwerks.

• Beispiel WWW

  Zur Unterstützung von Benutzern des WWWs bei der Suche werden bereits Lösungen angeboten. Diese sind aber alles andere als zufriedenstellend. Die Präsentation von Suchergebnissen und deren Qualität ist in Relation zur tatsächlichen Struktur des WWWs unstrukturiert und schwer zu bewerten. Die Verbesserung von Suchverfahren durch Einbeziehung von Hintergrundwissen über die Linkstrukturen oder das Benutzerverhalten, oder die Unterstützung des Benutzers durch Visualisierung der Suchergebnisse stellen schon für das momentan existierende WWW sehr anspruchsvolle Anforderungen an die Algorithmik. Wir können allerdings davon ausgehen, dass wir schon in kurzer Zeit mit einem wesentlich größeren WWW konfrontiert sind, dessen Schnelllebigkeit bzw. fortwährende Veränderung zusätzliche Probleme aufwirft.

• Beispiel Mobile Kommunikationsnetzwerke

  Die Telekommunikation hat sich durch die rasante Entwicklung der mobilen, drahtlosen Kommunikation (Mobiltelefone) zu einem der derzeitig am stärksten wachsenden Märkte entwickelt. Entsprechend steigen die Anforderungen an die Platzierung und Leistungsfähigkeit von Sende/Empfang-Stationen und Kommunikationsprotokollen. Zurzeit werden Methoden angedacht, die Funktionalität von Mobiltelefonen so zu erweitern, dass sie Aufgaben von Sende/Empfang-Stationen übernehmen und diese etwa in Ballungsgebieten ersetzen können. Die hier entstehenden dynamischen Netzwerke liefern neue Sichtweisen auf und neue Herausforderungen an die Forschung über Netzwerke: Die Lösung von Netzwerkproblemen wird eine dynamische Aufgabe, z.B. muss nun ein einmal etablierter Kommunikationsweg zwischen zwei Knoten ständig aktualisiert werden. Zudem stellt die Kombination aus Größe und Dynamik solcher Netzwerke völlig neue Fragen an Repräsentation, Speicherung und Visualisierung.

• Beispiel Soziale Netze

  In ganz neue und spannende Gebiete führen netzwerkbasierte Anwendungen, die bisher nicht unter einem algorithmischen Aspekt betrachtet wurden. Dies gilt beispielsweise für die Analyse von Sozialen Netzwerken ein Gebiet, das innerhalb der Sozialwissenschaften von wachsender Bedeutung ist. Für eine Analyse relevante Parameter wie Zentralität in Netzwerken, Gruppenbildung, verschiedene Beziehungsarten derselben Akteursmenge oder der Vergleich verschiedener Netzwerke prägen die Komplexität solcher Netzwerke Die automatische Generierung graphischer Darstellungen zur Unterstützung der Analyse führt zu neuen algorithmischen Fragen bei der Visualisierung komplexer Netzwerke.

Ziel dieses Schwerpunktprogramms ist es, die Forschung in der Algorithmik voranzutreiben und deren Anwendungspotential zu erweitern. Grundlegende Methoden der Algorithmentheorie sollen unter dem Blickwinkel aktueller, durch Anwendungen geprägter Aspekte weiterentwickelt werden. Bewusst wird mit der Ausrichtung auf netzwerkbasierte Probleme ein algorithmisches Gebiet fokussiert, das einerseits aufgrund seiner vielfältigen Anwendungen von großer Relevanz ist, andererseits in besonderer Weise neue algorithmische Aspekte und aktuelle methodische Entwicklungen der Algorithmik widerspiegelt. Die Erschließung neuer diskreter algorithmischer Methoden ist vor allem durch die Fokussierung auf große und komplexe Netzwerke zu erwarten. Neue Erkenntnisse in diesem Zusammenhang werden sich auch auf andere algorithmische Bereiche und entsprechende Anwendungsgebiete übertragen lassen. Für einige der hier angesprochenen Probleme sind zwar Lösungsvorschläge greifbar, allerdings sind diese meist unbefriedigend, wenn nicht sogar schlecht. Es geht darum, bessere, methodisch wohldurchdachte und langfristig wirksame Lösungen zu entwickeln.

Nicht zuletzt wegen der ausdrücklich gewünschten Orientierung des Schwerpunktprogramms an Fragestellungen aus konkreten Anwendungen ist eine Einbeziehung von Methoden des Algorithm Engineering geplant, einem sehr jungen Teilgebiet der Algorithmik, das alle Aspekte der tatsächlichen praktischen Umsetzbarkeit von Algorithmen, angefangen bei der mathematischen Modellierung von Anwendungsproblemen, über den theoretischen Algorithmenentwurf und die Algorithmenimplementation, bis hin zum empirischen Algorithmenentwurf, der experimentellen Erforschung von Algorithmen und der systematischen Untersuchung des Verhaltens von Algorithmen bei Praxisdaten umfasst. Erst seit wenigen Jahren finden derartige Themen verstärkt Eingang in die algorithmisch orientierte Forschung. Das geplante Schwerpunktprogramm soll diese Entwicklung weiter vorantreiben.

Durch das Programm soll eine gegenseitige Befruchtung zwischen verschiedenen Projekten forciert werden. Es ermöglicht den wechselseitigen Austausch zwischen konkreten, aus Anwendungen motivierten Projekten und übergreifenden Querschnittsprojekten.