B.Sc./ M.Sc. Thesis: Visualization-driven graph data reduction

Type of thesis: Masterarbeit / location: Leipzig / Status of thesis: Theses in progress

Existing graph visualizations usually are unsuitable for visualizing Big GraphData due to the large node and edge sets.  Due to the very large graphs it will not be possible to draw a complete graph with all its nodes and edges in the UI. In this work we plan to examine visualization-driven adaptation of queries to very large graphs. Visualization-driven means that the display parameters of the user and the visual capabilities of the human are taken into account when querying data. Only the necessary amount of data should send to a client that draws nodes and edges. To achieve that goal methods for sampling, summarization and aggregation could be investigated. In the field of classical charting first research ideas were presented recently. For large graphs the project enters new fronteers.

In this Master thesis we would like to evaluate how graph fragments could be filtered and how graph layouts could be prcalculated in the execution layer of a graph store. We would initially like to filter of nodes in the big data system based on the number of pixels available in the visualization. The number of pixels, potentially supplemented by a perceptual model of the human specifies which node / edge a person can differentiate. Consequently less nodes and edges can be transferred, possibly represented by even smaller contiguous areas for very dense parts of a graph. Closely spaced edges and nodes can be hidden without causing a noticeable reduction in information for the user. Ideally, these nodes and edges are filtered already in the request to the Graph-framework so that they never levaed the Big Data System. Similar approaches have been applied for time series and provide great potential in the visualization of very large graphs.

The thesis consist of the following subtasks

  • getting an overview related work – how is graph visualization for large graphs currently handled
  • Concept of a visualization driven data reduction approach
  • Prototypical implementation or a graph reduction approach, precomputed layouting (if possible in distributed system)
  • Evaluation, definition of a simple quality metrics to measure loss for a user


Dr. Eric Peukert

Stellvertretender Geschäftsführer

Fakultät Mathematik und Informatik

Universität Leipzig