Institut für Theoretische Informatik, Algorithmik

Heuristische Verfahren zur Visualisierung dynamischer Netzwerke

Mitarbeiter

Förderung

Beschreibung

In vielen Bereichen liegen Daten auf natürliche Art und Weise in Form von Netzwerken vor. Beispiele sind soziale Netzwerke, UML-Diagramme in der Softwareentwicklung oder phylogenetische Bäume in der Biologie. Um Netzwerke zu analysieren und für Menschen verständlich darzustellen, sind Algorithmen zur Visualisierung von Netzwerken unerlässlich. Oftmals sind Netzwerke jedoch nicht statischer sondern dynamischer Natur, wie zum Beispiel soziale Netzwerke, die sich über die Zeit verändern. In dynamischen Netzwerken ist es von Interesse, nicht nur die Daten zu einem bestimmten Zeitpunkt, sondern ihre Änderungen darzustellen. Im Beispiel eines sozialen Netzwerks ist es interessant zu verstehen, wie bestimmte Ereignisse die Struktur des Netzwerks beeinflussen.

Verwendet man einen statischen Algorithmus der bestimmte ästhetische Kriterien optimiert um ein dynamisches Netzwerk zu verschiedenen Zeitpunkten zu visualisieren, so erhält man im Allgemeinen sich deutlich unterscheidende Visualisierungen, auch wenn sich das Netzwerk nur leicht verändert hat. Kleine und lokale Änderungen der Struktur können die Optimalität einer Visualisierung also stark und global beeinflussen. Daher eignen sich die bisher entwickelten statischen Algorithmen nicht um Veränderungen in einem dynamischen Netzwerk herauszuarbeiten.

Aus diesem Grund ist die Visualisierung von dynamischen Netzwerken seit etwa zehn Jahren ein wichtiges Forschungsgebiet mit einigen sehr populären theoretischen Fragestellungen, allen voran die simultane Zeichenbarkeit mehrerer Netzwerke. Die bisher bekannten theoretischen Resultate bilden eine wichtige Grundlage für weitere Forschung, sie sind aber leider sehr weit von praxistauglichen Verfahren entfernt. Im Zuge dieses Projekts sollen heuristische Verfahren zur Visualisierung von dynamischen Netzwerken entwickelt, implementiert und getestet werden, wobei heuristisch bedeutet, dass diese Verfahren nicht vorwiegend auf beweisbare Gütegarantien abzielen, sondern in der Praxis gute Ergebnisse liefern.

Hiwi-Stellen

Im Rahmen diese Projekts sind mehrere HiWi-Stellen zu vergeben.

Das Projekt ist mittlerweile abgeschlossen.