Fahnenschreiber, Sebastian (2012)
Graph Layout Algorithm based on Maximum Entropy Unfolding.
Technische Universität Darmstadt
Bachelorarbeit, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Bachelorarbeit |
|---|---|
| Erschienen: | 2012 |
| Autor(en): | Fahnenschreiber, Sebastian |
| Art des Eintrags: | Bibliographie |
| Titel: | Graph Layout Algorithm based on Maximum Entropy Unfolding |
| Sprache: | Englisch |
| Publikationsjahr: | 2012 |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Forschungsgruppe Visual Search and Analysis (VISA), Graph visualization, Visual graph analysis, Dimension reduction |
| Zusätzliche Informationen: | 56 p. |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Graphisch-Interaktive Systeme |
| Hinterlegungsdatum: | 12 Nov 2018 11:16 |
| Letzte Änderung: | 12 Nov 2018 11:16 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum