DynamicGraphs - Inkrementelle Graphentheoretische Analyse Dynamischer Systeme

01.01.2013 -

Abgeschlossen
TU Darmstadt & Siemens AG

Name des Teilnehmers: Benjamin Schiller

Beschreibung des IT-Forschungsprojekts: Viele Systeme können als Graphen modelliert werden. Bekannte Beispiele sind Computer Netzwerke, in denen jeder Rechner durch einen Knoten und jede Verbindung zwischen zwei Rechnern durch eine Kante repräsentiert wird. Analog dazu können auch die Nutzer und ihre Beziehungen in Sozialen Netzwerken wie Facebook, Twitter oder Google Plus als Graphen modelliert werden. Die Nutzer werden als Knoten im Graphen repräsentiert und ihre Beziehungen als Kanten modelliert: ungerichtete Kanten zur Beschreibung von Freundschaftsbeziehungen in Systemen wie Facebook und gerichtete Kanten zur Beschreibung von Follower Beziehungen in Netzwerken wie Twitter oder Google Plus. Ein weiteres Beispiel sind Straßennetzwerke. Um diese als Graph zu modellieren, können Kreuzungen als Knoten und Straßen als Kanten zwischen diesen abgebildet werden.

Im Rahmen des Projekts Dynamic Graphs sollen Verfahren und Algorithmen entwickelt werden, die eine effiziente Analyse von großen Systemen erlauben, indem diese als Graphen modelliert und ihre Eigenschaften anhand graphentheoretischer Analysen bestimmt werden. Während diese Verfahren Anwendung in der Analyse gesammelter Datensätze finden, liegt der Fokus dieses Projekt auf der Analyse von sich weiterhin (live)

verändernden Systemen und der Berechnung sowie Abschätzung ihrer Eigenschaften anhand einer inkrementellen graphentheoretischen Analyse. Als Anwendungsfall hierfür dient die Erkennung von Anomalien im Verkehrsfluss von Großstädten. Um dies zu ermöglichen sollen zunächst Messdaten diverser Sensoren sowie Informationen über den Verkehrsfluss als Graph modelliert werden. Die kontinuierliche Analyse dieses sich verändernden Graphen soll dann Aufschlüsse darüber erlauben, ob Anomalien auftreten, sich Staus bilden oder die Entwicklung solcher Ereignisse bevorsteht. Mit dieser Methodik gewonnene Erkenntnisse über die

Entwicklung des Verkehrsaufkommens können zur Echtzeit?Indikation von Problemen, Optimierung des Verkehrsflusses sowie Verbesserung von Routenplanung verwendet werden.

Software Campus-Partner: TU Darmstadt, Siemens AG

Umsetzungszeitraum: 01.01.2013 - 31.12.2014