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

Schwerpunktprogramm (SPP) 1126
der Deutschen Forschungsgemeinschaft (DFG)

Algorithmik großer und komplexer Netzwerke

Flexible und adaptive abstrahierende Darstellung großer Netzwerke

Zusammenfassung

In diesem Projekt soll die hierarchische Visualisierung großer Netzwerke untersucht werden. Grundlage hierfür ist die Partition der Netzwerke in geeignete Teilmengen.
Der erste Abschnitt des Projekts konzentriert sich daher primär auf die Analyse und Weiterentwicklung von Partitionierungstechniken für Graphmodelle. Diese Modelle sollen reale große Datenmengen wie soziale Netzwerke oder das Internet ausreichend charakterisieren.
Der zweite Teil der Arbeiten beschäftigt sich mit der Realisierung der hierarchischen Darstellung. Der Schwerpunkt liegt dabei auf der Dynamisierung, das heisst, dass sowohl die hierarchische Zergliederung als auch der zugrundeliegende Graph während der Betrachtung veränderbar sein sollen. Das Ziel besteht einerseits darin, eine Visualisierung zu erzielen, die die Modifikationen in einer konsistenten und harmonischen Form wiedergibt. Andererseits soll eine komplexe Neuberechnung der Partitionen nach jedem Schritt durch eine Wiederverwendung alter Berechnungsergebnisse umgangen werden. Neben den Analysen soll hierfür eine Datenstruktur zur gleichzeitigen Speicherung der Hierarchie sowie der Berechnungsergebnisse entwickelt werden. Darauf kann dann eine effiziente Visualisierung, die den gewünschten Anforderungen entspricht, aufgebaut werden.

Stand der Forschung und eigene Vorarbeiten

Ziele und Arbeitsprogramm

Literatur

Organisatorisches

Beteiligte Personen

Vortrag (pdf) auf dem 1. Jahres-Kolloquium (Konstanz, 22.-24. Juli 2002)

Vortrag (pdf) auf dem Workshop "Internet-Graphen" (Tübingen, 18. Oktober 2002)

Vortrag (pdf) auf dem 2. Jahres-Kolloquium (Tübingen, 26.-28. März 2003)