TU Darmstadt / ULB / TUbiblio

Graph Layout Algorithm based on Maximum Entropy Unfolding

Fahnenschreiber, Sebastian (2012):
Graph Layout Algorithm based on Maximum Entropy Unfolding.
TU Darmstadt, [Bachelor Thesis]

Abstract

In this bachelor thesis, I present a new graph visualization method. My approach is based on the maximum entropy unfolding (MEU) dimension reduction technique, which is modified to include the structure of the graph into its computations. The layout for the resulting nodelink diagram is produced by reducing the high dimensional features vectors of vertices in a multivariate graph to two-dimensional coordinates. Since experiments showed, that the raw edge structure of a graph is not always sufficient for MEU to produce good results, heuristics for better computation structures are introduced. A first heuristic is based on transitive connections in the graph and a second one combines feature similarity and the adjacency of vertices. The evaluation compares the layouts, which were computed with both heuristics with a number other graph layouts and shows that graph layouts based on local dimension reduction techniques can be of great value of visual graph analysis. In dieser Bachelor Thesis werde ich eine neue Methode zur Visualisierung von Graphen vorstellen. Mein Ansatz basiert auf Maximum Entropy Unfolding, einer Technik zur Dimensionsreduktion. Der Algorithmus wurde modifiziert, sodass er die Struktur des Graphen in die Berechnungen einbezieht. Die hochdimensionalen Feature-Vektoren der Knoten im multivariaten Graph werden auf zweidimensionale Koordinaten reduziert, welche die Grundlage für ein Node-Link Diagramm bilden. Da deutlich wurde, dass MEU nicht immer in der Lage ist direkt aus der Kantenstruktur des Graphs ein gutes Layout zu erzeugen, werden Heuristiken zum Finden einer besseren Berechnungsgrundlage eingeführt. Eine erste Heuristik basiert auf transitiven Verbindungen im Graph, während eine Zweite die Ähnlichkeit der Features und die Adjazenz von Knoten kombiniert. Die Auswertung, welche Resultate der beiden Heuristiken mit einer Anzahl anderer Layout Algorithmen vergleicht, zeigt, dass lokale Techniken zur Dimensionsreduktion von großem Wert für die visuelle Graphenanalyse sein können.

Item Type: Bachelor Thesis
Erschienen: 2012
Creators: Fahnenschreiber, Sebastian
Title: Graph Layout Algorithm based on Maximum Entropy Unfolding
Language: English
Abstract:

In this bachelor thesis, I present a new graph visualization method. My approach is based on the maximum entropy unfolding (MEU) dimension reduction technique, which is modified to include the structure of the graph into its computations. The layout for the resulting nodelink diagram is produced by reducing the high dimensional features vectors of vertices in a multivariate graph to two-dimensional coordinates. Since experiments showed, that the raw edge structure of a graph is not always sufficient for MEU to produce good results, heuristics for better computation structures are introduced. A first heuristic is based on transitive connections in the graph and a second one combines feature similarity and the adjacency of vertices. The evaluation compares the layouts, which were computed with both heuristics with a number other graph layouts and shows that graph layouts based on local dimension reduction techniques can be of great value of visual graph analysis. In dieser Bachelor Thesis werde ich eine neue Methode zur Visualisierung von Graphen vorstellen. Mein Ansatz basiert auf Maximum Entropy Unfolding, einer Technik zur Dimensionsreduktion. Der Algorithmus wurde modifiziert, sodass er die Struktur des Graphen in die Berechnungen einbezieht. Die hochdimensionalen Feature-Vektoren der Knoten im multivariaten Graph werden auf zweidimensionale Koordinaten reduziert, welche die Grundlage für ein Node-Link Diagramm bilden. Da deutlich wurde, dass MEU nicht immer in der Lage ist direkt aus der Kantenstruktur des Graphs ein gutes Layout zu erzeugen, werden Heuristiken zum Finden einer besseren Berechnungsgrundlage eingeführt. Eine erste Heuristik basiert auf transitiven Verbindungen im Graph, während eine Zweite die Ähnlichkeit der Features und die Adjazenz von Knoten kombiniert. Die Auswertung, welche Resultate der beiden Heuristiken mit einer Anzahl anderer Layout Algorithmen vergleicht, zeigt, dass lokale Techniken zur Dimensionsreduktion von großem Wert für die visuelle Graphenanalyse sein können.

Uncontrolled Keywords: Forschungsgruppe Visual Search and Analysis (VISA), Graph visualization, Visual graph analysis, Dimension reduction
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Interactive Graphics Systems
Date Deposited: 12 Nov 2018 11:16
Additional Information:

56 p.

Export:

Optionen (nur für Redakteure)

View Item View Item