Visualization of dynamic graphs

Abstract

A dynamic graph is built from a Cartesian set V(t) × E(t) where V(t) and E(t) denote the set of vertices and edges at time t, respectively. Since changes often happen at massive local parts of the graph, it is difficult to capture and understand them. Visualization of dynamic graphs can alleviate the difficulty as it maps changes to graphics that can be better perceived by people. In visualization, graphs are usually drawn as node-link or matrix diagrams, and the temporal dimension is represented by timelines or animations. Based on these visualization techniques, various developments have been made, from providing a layout algorithm that optimizes the visual stability to applying analysis to real-world datasets of different disciplines. This thesis aims at investigating previous work in the area of visualizing dynamic graphs, and then concentrating on discovering structural and semantical patterns from dynamic graphs. Specific contributions are as follows. First, we provide a method of searching large graphs for special topologies. The method conducts Community Detection to obtain components of manageable sizes, then classifies them according to their structures. Second, we investigate the dynamics of attributes of graph entities. Specifically, we implement an application of deriving functionalities of geographical regions by analysing a temporal network constructed from geotextual data. Natural Language Processing techniques are used to deal with the textual part of attributes. Third, we improve the usability of traditional animations and timelines. To help users compare adjacent frames of the animation, glyphs of two timestamps are placed concentrically in one view. Meanwhile, visual changes caused by the glyph transformation is minimized by a pentagonal design. In timelines, identical objects at all timestamps are identifed and linked chronologically to facilitate the tracing of object evolution.