Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification
On this page, you can find my Master's Thesis, supplementary material and errata.
Keywords: aesthetics, graph drawing, machine learning
Contents
Abstract
Visualizing relational data as drawing of graphs is a technique in very wide-spread use across many fields and professions. While many graph drawing algorithms have been proposed to automatically generate a supposedly high-quality picture from an abstract mathematical data structure, the graph drawing community is still searching for a way to quantify the aesthetic value of any given solution in a way that allows one to compare graph layouts created by different algorithms for the same graph (presumably to automatically choose the better one). We believe that one promising path towards this goal could be enabled by combining data analysis techniques that have proven useful in other scientific disciplines that are dealing with large structures such as astronomy, crystallography or thermodynamics. In this work we present an initial investigation of some statistical properties of graph layouts that we believe could provide viable syndromes for the aesthetic value. As a proof of concept, we used machine learning techniques to train a neural network with the results of our data analysis and thereby built a model that is able to discriminate between better and worse layouts with an accuracy of 95 %. A rudimentary evaluation of the model was performed and is presented. This work primarily provides an infrastructure to enable further experimentation on the topic and will be made available to the public as Free Software.
Citation
This work may be cited as:
Moritz Klammler. “Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification”. Master's thesis. Karlsruhe Institute of Technology, 2018. http://klammler.eu/msc/
The following BibTeX entry might come handy:
@Thesis{Klammler2018,
author = "Klammler, Moritz",
title = "Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification",
school = "Karlsruhe Institute of Technology",
year = "2018",
month = "3",
type = "master's thesis",
address = "Karlsruhe, Germany",
url = "http://klammler.eu/msc/",
}
Downloads
The following files may be freely downloaded and redistributed by anybody without asking for permission. Additional permissions may be granted in a copyright notice included in the individual files.
| File | Size | Type | Description | Signature |
|---|---|---|---|---|
| thesis.pdf | 5.9 MiB | application/pdf | full text of the thesis | thesis.pdf.sig |
| slides.pdf | 5.1 MiB | application/pdf | presentation slides | slides.pdf.sig |
| graphstudy.tar.bz2 | 1.5 MiB | application/octet-stream | compressed source code archive | graphstudy.tar.bz2.sig |
We continue development on the code that was written during the preparation of this thesis as a public GitHub repository.
We also submitted a paper to GD'18 which – as it so happens – has won a “Best Paper Award”. You can download the extended version of the paper from arXiv. The presentation slides for the talk given at the conference are available here. Note that you can find the source code for all publications in the repository.
Errata
Did you find an error that is not mentioned below? Please tell me about it (and whether you would object to being acknowledged here for reporting it).
Only errors that might affect understanding, not just simple spelling and grammar mistakes (There are just too many of them!) will be mentioned. Insights that things should have better be done entirely differently also won't be listed as errata but might make for a good topic of your own thesis.
-
The cost for computing the
ANGULARproperty using the described algorithm of a graph with n vertices and m edges is Ο(m log(m)) ⊆ Ο(n2 log(n)) in the worst case (of a fully connected graph) and not Ο(m) as stated in the thesis. The logarithmic factor is due to the sorting of the polar angles. - In equation 7.12 on page 86 the integral should be over f(x) log(f(x)) rather than x log(x).
