LEA TU München, Institut für Informatik
Lehrstuhl für Effiziente Algorithmen 		DFG Logo

Ziele und Arbeitsprogramm

  1. Ziele
  2. Arbeitsprogramm
    1. Analyse zur Strukturabhängigkeit von Partitionierungstechniken
    2. Erkennung von speziellen Strukturen / Eigenschaften
    3. Strukturabhängige Algorithmenoptimierung
    4. Parametrisierte Komplexitätsanalysen für Partitionierungsprobleme
    5. Adaptive Partitionierung von variablen Datensätzen
    6. Flexible Datenstrukturen zur Speicherung / Visualisierung von hierarchischen Daten
    7. Visualisierung von modifizierbaren hierarchischen Strukturen

Ziele

Ziel der geplanten Forschungsarbeit ist es, einerseits gezielte Analysen zur Strukturabhängigkeit von Algorithmen sowie zu Eigenschaften von Netzwerkmodellen für hierarchische Graphdarstellungen durchzuführen. Andererseits sollen Algorithmen und Datenstrukturen entwickelt werden, die eine effiziente hierarchische Darstellung von großen zeitlich veränderbaren Netzwerken ermöglichen.
Ausgehend von Untersuchungen zur Strukturabhängigkeit von Partitionierungstechniken, sowie Analysen von speziellen Graphmodellen in Bezug auf verborgene Strukturen und Eigenschaften sollen neue und effizientere Graphalgorithmen entstehen. Dabei handelt es sich einerseits um Verbesserungen von herkömmlichen Methoden sowie um speziell angepasste Neuentwicklungen. Ein Schwerpunkt in diesem Teil des Arbeitsprogramms sind Partitionierungstechniken. Für diese sollen durch parametrisierte Komplexitätsanalysen neue Erkenntnisse über das Laufzeitverhalten und die Schwierigkeit gewonnen werden.
Im Bereich Visualisierung wird erforscht, wie Ergebnisse von alten Graphpartitionierungen wiederverwendet werden können, um eine neue Partition für veränderte Bewertungen bzw. modifizierte Graphen zu berechnen (siehe Adaptive Partitionierung). Daraus entstehende Anforderungen werden in eine Datenstruktur eingearbeitet, die somit eine Grundlage für effiziente Berechnungen darstellt und ferner das Speichern von hierarchischen Darstellungen des Graphen ermöglicht. Darauf aufbauend werden nun Verfahren und Algorithmen entwickelt, um eine dynamische Visualisierung großer hierarchischer Graphen zu ermöglichen. Besonderer Wert wird dabei auf die dynamische Komponente gelegt, d.h. der Betrachter erhält eine Folge von untereinander stimmigen Darstellungen.

Arbeitsprogramm

Nachfolgend werden die einzelnen Teile des Arbeitsprogramms erläutert.

Analyse zur Strukturabhängigkeit von Partitionierungstechniken

Wesentliche Grundvoraussetzung für eine gezielte Verbesserung bzw. Weiterentwicklung von Partitionierungstechniken ist das detaillierte Verstehen der Funktionsweise und des Verhaltens eines Algorithmus bei speziellen Eigenschaften der Eingabedaten. Daher soll in diesem Arbeitspunkts analysiert werden, wie stark sich welche Grapheigenschaften auf die Ergebnisse von bekannten Partitionierungstechniken auswirken. Ein besonderes Augenmerk wird dabei auf die Wechselwirkung der verschiedenen Einflussfaktoren gerichtet.
Ziel ist es, die Güte von Partitionierungsalgorithmen in Abhängigkeit von Eingabegraphen zu bestimmen. Diese Beobachtungen werden für die Abschätzung von verbesserten Schranken verwendet. Ferner wird versucht, durch Verknüpfung der sich abzeichnenden Vorzüge verschiedener Techniken ein neues Verfahren zu entwickeln. Dieses Verfahren soll dann für spezielle Graphklassen (als Ziel stehen hier die Small World Graphen) ein besseres Ergebnis als herkömmliche Verfahren liefern.
Zu den zu untersuchenden Eigenschaften zählen Zusammenhang, Dichte und Verteilung der Knotengrade. Diese Auswahl, die lediglich eine Anfangsmenge darstellt, ergibt sich aus dem aktuellen Stand der Forschung. Diese Werte stehen entweder für erfolgversprechende Graphklassen oder dienen als Grundlage für relevante Partitionierungstechniken.

Erkennung von speziellen Strukturen / Eigenschaften

Wie bereits in [Stand der Forschung] dargestellt, ist es von großem Interesse, geeignete Graphmodelle bzw. Graphklassen zu analysieren. In diesem Projekt soll dies im Speziellen für die Klasse der Small World Graphen geschehen. Ferner werden bei entsprechenden Ergebnissen neue Modelle definiert, falls dadurch ermöglicht wird, detailliertere Aussagen zu treffen.
Die zu analysierenden Eigenschaften werden weitestgehend in Anlehnung an die Resultate aus dem Bereich Strukturabhängigkeit gewählt werden. Besonderes Augenmerk wird auf jedem Fall folgenden Schwerpunkten gewidmet sein:

Strukturabhängige Algorithmenoptimierung

In enger Anlehnung an die Ergebnisse aus [Strukturabhängigkeit] und [Eigenschaften] soll nun an Graphalgorithmen gearbeitet werden. Der Schwerpunkt liegt sowohl auf der Analyse als auch der Neu- und Weiterentwicklung von Algorithmen. Die Analysen beziehen sich nun nicht nur auf reine Partitionierungsprobleme sondern sind weitreichender und beinhalten Problemstellungen, wie sie beispielsweise aus dem Bereich der Kommunikationsnetze bekannt sind. Neben der rein algorithmischen Herausforderung können diese Ergebnisse auch für die Entwicklung von neuen Datenstrukturen für hierarchische Graphen sowie bei der Visualisierung solcher Strukturen (siehe [Datenstrukturen] und [Dynamische Visualisierung]) zum Tragen kommen.
Die Untersuchungen lassen sich in wie folgt aufspalten:

Parametrisierte Komplexitätsanalysen für Partitionierungsprobleme

Wie bereits in [Partitionierung] beschrieben, sind Partitionierungsprobleme in der Regel NP-vollständig, zumindest jene, die für die Partitionierung von großen Netzwerken in Frage kommen. Aus diesem Grund handelt es sich bei den hierfür eingesetzten Algorithmen nicht um exakte Lösungen, sondern um Approximationen.
Mit Hilfe von parametrisierter Komplexität [DFS99] soll eine neue Betrachtung der Partitionierungsprobleme versucht werden. Grundgedanke der parametrisierten Komplexität ist es, diejenigen Faktoren eines Problems herauszustellen, die für die Schwierigkeit des Problems verantwortlich sind. Besondere Anwendung findet diese Betrachtungsweise im Bereich der NP-harte Probleme. Durch Angabe von parametrisierten Schranken kann eine aussagekräftiger Aussage über die Laufzeit bei entsprechender Parameterwahl getroffen werden.
Dieser Ansatz verspricht zwar keinen polynomiellen Algorithmus, bietet jedoch zwei entscheidende Vorteile. Einerseits kann man, wenn man sich in der Wahl des für die Komplexität ausschlaggebenden Parameters auf einen kleinen Wertebereich beschränkt, immer noch relativ schnelle Algorithmen erhalten. Durch Einschränkung des Parameters besteht beispielsweise die Möglichkeit, dass der Algorithmus selbst für große Netzwerke eine akzeptable Laufzeit besitzt. Andererseits konnten bereits in der Vergangenheit derartige Informationen eingesetzt werden, um neue Aussagen über die Schwierigkeit der Probleme zu finden.
Um eine bessere Einstufung für die Schwierigkeit der Probleme zu finden, wurde im Bereich der parametrisierten Komplexitätsanalyse eine eigene Hierarchie eingeführt. Mit ihr sind Resultate zur so genannten parametric intractability erzielt worden. Unter Zuhilfenahme dieser Techniken hat man nun einen neuen Ansatz entwickelt, um Aussagen über die Approximierbarkeit von Problemen zu treffen. In diesem Projekt soll nun derselbe Ansatz verwendet werden, um entsprechende Ergebnisse für das Problem der Graphpartitionierung zu erhalten.

Adaptive Partitionierung von variablen Datensätzen

In diesem Teil des Arbeitsprogramms geht es um die Frage, wie die Partitionierung eines Graphen variabel in der Wahl der Bewertungsfunktion und stabil gegenüber Modifikationen des Graphen gestaltet werden kann.
Ziel dieses Vorgehens ist es, zu einem gegebenen Partitionierungsverfahren und einer gegebenen Partition dynamisch auf Änderungen der Bewertungsfunktion reagieren zu können. Diese Reaktion soll möglichst wenig Rechenarbeit nach sich ziehen. D.h. es soll möglichst viel Information aus der alten Berechnung der Partitionierung wiederverwendet werden. Analog soll dies für eine Änderung der Gewichte in den Graphdaten durchführbar sein.
Idealerweise würde das Ergebnis eine Umformung einer gegebenen Partitionierung bedeuten. Eine Möglichkeit, dies zu bewerkstelligen, besteht darin, neben der Partition zusätzliche Informationen aus dem Partitionierungsprozeß zu speichern, um diese bei der Umformung wiederzuverwenden. Es ist jedoch sehr wahrscheinlich, dass dies nicht oder nur für sehr spezielle Algorithmen und Graphen ohne zusätzlichen Nachberechnungen möglich ist. Bessere Aussagen kann man jedoch erwarten, wenn man zusätzliche Berechnungen erlaubt, um eine approximierte Partition zu erhalten. In solchen Fällen ist das erhoffte Ergebnis eine qualitative Aussagen über die Güte der neuen Partitionierung. Ziel sollte es sein, eine möglichst allgemeine Aussage für solche Modifikationen zu erhalten. D.h. abhängig von der Änderung der Bewertungsfunktion sollen Schranken für die Abweichung der approximierten Lösung von einer optimalen Umformung angegeben werden. Idealerweise würden Aussagen gefunden, die sich auf einzelne Teilgraphen beziehen. Dies bedeutet, dass die Qualität Partitionierung des restlichen Graphen in der Approximation und in der optimalen Lösung identisch sind. Diese Information könnte dann dazu verwendet werden, bei besonders schlechten Approximationsergebnissen die Partitionierung nur für einige Teile des Graphen lokal nachzuberechnen.
An diese Stelle kommt der zweite Teil der Untersuchungen zum Tragen. Dieser besteht darin, zu erforschen, wie eine lokale Teilberechnung des Partitionierungsproblems durchgeführt werden kann. Sicherlich genügt es nicht, eine feste Knotenmenge anzugeben und für den durch sie induzierten Teilgraphen die Berechnung zu starten. Vielmehr muss an dieser Stelle die Nachbarschaft der Knoten einbezogen werden. Erstes Ziel ist daher ein Verfahren, das ausgehend von einer Knotenmenge eine möglichst gute Neuberechnung erzielt, ohne die berücksichtigte Menge der Knoten unnötig zu vergrößern. Eine wichtige Rolle spielen hierbei sowohl die Partitionierungsmethoden als auch die Bewertungsfunktion. Nicht vernachlässigbar sind ebenfalls die Parameter, die in die Bewertungsfunktion eingehen. Es bleibt also zu untersuchen, wie beispielsweise die Größe oder Schwankungen der Kantengewichte für das Ergebnis des Prozesses ausschlaggebend sind.
Ähnlich wie bei der Modifikation der Bewertungsfunktion und der Gewichte, soll ebenfalls eine Aussage über eine topologische Änderung des Graphen gefunden werden. Um dies durchzuführen ist es wichtig, ein Maß für die topologische Änderung zu definieren. Die Notwendigkeit hierfür kann man leicht an folgendem Beispiel sehen. Das Einfügen einer zusätzlichen Kante in einem Kreis kann diesen entweder in zwei gleichgroße Teile zerteilen (große topologische Änderung) oder aber nur eine geringe lokale Änderung bewirken, wenn sie zwischen zwei Knoten eingefügt wird, die über nur wenige Zwischenknoten verbunden sind.
Aus den Ergebnissen zur Untersuchung der adaptiven Partitionierung von Graphen kann man einige Anforderungen an Datenstrukturen ableiten, die zur Speicherung von hierarchischen Daten verwendet werden (siehe [Datenstrukturen]). Auch eine Modifikation von Partitionierungstechniken in der Art und Weise, dass lokale Neuberechnungen nur in geringem Maße notwendig sind, ist denkbar.

Flexible Datenstrukturen zur Speicherung / Visualisierung von hierarchischen Daten

Bei der Arbeit mit hierarchischen Graphdaten ist es oft wünschenswert, dass man diese auch nach dem Anlegen modifizieren kann. Neben dem reinen Hinzufügen und Entfernen von Knoten und Kanten ist in diesem Fall auch ein Migrieren von Knoten von einer Organisationseinheit des Hierarchiebaums in eine andere Einheit wichtig. Solche Modifikationen bedeuten nicht nur ein reines Verschieben, sondern können ebenfalls eine Vielzahl von weiteren Verwaltungsaufgaben nach sich ziehen. So müssen zum Beispiel Referenzen für Nachbarschaftsbeziehungen innerhalb der Einheiten, Relationen wie über- oder untergeordnete Ebenen und eine Vielzahl vergleichbarer Beziehungen angepasst werden.
Diese erwähnten Modifikationen implizieren nur Änderungen einzelner Graphenobjekte. Ein weiterer wichtiger Punkt sind mögliche Änderungen der Hierarchie selbst. Hierzu zählen das Zusammenfassen bzw. Aufspalten von Einheiten oder ganzen Ebenen. Eine rein iterative Lösung dieses Problems durch zahlreiche Einzelschritte scheint hier nicht akzeptabel. An dieser Stelle soll mit einem globaleren Verständnis an das Problem herangegangen und eine umfassende Lösung gefunden werden. Ziel dieses Arbeitspunktes ist unter anderem eine effiziente Umsetzung dieser Forderungen.
Neben all diesen Anforderungen an die Datenstruktur zur Simulation von Operationen kann es ferner wichtig sein, zusätzliche Informationen zu speichern. Einige Beispiele hierfür wurden bereits in [Adaptive Partitionierung] genannt. Sind durch Änderungen in der Hierarchie auch Veränderungen in den Zusatzinformationen nötig, so kommt Bedarf an zusätzlichen weitgreifenden Überlegungen auf. Somit sind in der zu Datenstruktur ebenfalls effiziente Möglichkeiten zur Speicherung und globalen Anpassung von Zusatzinformationen zu integrieren.
Ein weiterer Punkt, der in die Gestaltung der Datenstruktur einfließen wird, kommt aus dem Bereich der Visualisierung. Um Navigation durch die Hierarchie zu ermöglichen, ist es beispielsweise wichtig, schnell den aktuellen Fokus in der hierarchischen Darstellung wechseln (horizontale und vertikale Navigation), sowie die Größe des Fokus ändern zu können (Zoom in/out).
All diese Anforderungen lassen erkennen, dass es sich bei der Entwicklung einer geeigneten Datenstruktur um eine umfangreiche und wichtige Arbeit handelt. Sie bildet daher einen der Schwerpunkte dieses Antrags.

Visualisierung von modifizierbaren hierarchischen Strukturen

Dieser Teil der Arbeit beschäftigt sich mit einer benutzergerechten Visualisierung von sich dynamisch ändernden hierarchischen Strukturen. Unter Verwendung einer geeigneten Datenstruktur soll es möglich sein, den zugrundeliegenden Graphen oder die hierarchische Anordnung so zu verändern, dass ein Betrachter diese Modifikationen mitverfolgen kann bzw. durch Änderungen nicht den Überblick verliert (``preserving of the mental map''). Es ist hierbei prinzipiell zwischen zwei verschiedenen Modifikationen zu unterscheiden. Einmal die, die der Betrachter selbst vornimmt, und jene, die automatisch von ``außen'' vorgenommen werden. Bei automatischen Modifikationen muss der Betrachter stärker geführt, also evtl. auf die Veränderungen hingewiesen werden.
Finden Veränderungen im aktuellen View des Betrachters statt, so dürfen diese nicht sprunghaft geschehen, sondern müssen einen kontinuierlichen Verlauf haben. Bei einer benutzerbedingten Modifikation wird in den meisten Fällen lediglich eine Anpassung innerhalb des Views notwendig sein. Es sollten dabei zwei Varianten optional wählbar sein, einerseits eine durch den Benutzer hervorgerufene Durchführung und andererseits eine automatische Korrektur des Layouts. In beiden Fällen sollte dabei ein möglichst gleichmäßiges Wandern der Knoten erfolgen. Bei Modifikationen außerhalb des Views kann auf diese sanften Übergänge verzichtet werden. Bei größeren Veränderungen muss der Betrachter jedoch durch eine Warnung bzw. Darstellung in einem weiteren Fenster in Kenntnis gesetzt werden. Eine geeignete Benachrichtigung (Färbung des entsprechenden Teilgraphen in einem Überblickfenster, Einblendung des Teilgraphen während der Modifikation, Wechsel bzw. Zoom out vom aktuellen View) soll vom Betrachter wählbar sein, bzw. je nach Umfang der Modifikation automatisch angestoßen werden.
Neben diesen allgemeinen Anforderungen ergeben sich einzelne Spezialfälle, für die eine geeignete Lösung gefunden werden muss. Es handelt sich hierbei um jene Problemfälle, die bereits bei der Konstruktion der hierarchischen Datenstruktur aufgetreten sind. Der Vollständigkeit halber seien sie nochmals exemplarisch erwähnt: Aufspalten/Hinzufügen von Einheiten auf einer Hierarchiestufe, Modifikationen über verschiedene Hierarchieebenen, schnelles Zoom in/out, horizontales/vertikales Navigieren.
Eine weitere Eigenschaft, die für die Visualisierung angestrebt ist, besteht darin, einzelne Abstraktionsebenen optisch zu verschmelzen. D.h. es soll möglich sein, einen Knoten durch den entsprechenden Teilgraphen auf der darunterliegenden Ebene zu ersetzen. Solche Verschmelzungen können sich auch über mehrere Ebenen erstrecken.
Ebenfalls angestrebt ist eine betrachterdefinierte Einstellung der verschiedenen Optionen. Somit soll gewährleistet sein, dass der Betrachter die hierarchische Darstellung derart nutzen kann, dass er individuell die Informationen hervorheben kann, die er gerade benötigt.
Ob eine Simulation von Veränderungen am Graphen innerhalb eines gewissen Zeitraums als eine Art "Movie" innerhalb des Antragszeitraums umsetzbar ist, hängt von den Ergebnissen in der Entwicklung ab, wird jedoch durchaus in Betracht gezogen.

Hanjo Täubig
Last modified: Thu Aug 29 13:29:48 CEST 2002