Stable visualization of connected components in dynamic graphs. (January 2021)

• Record Type: Journal Article
• Authors: Giacomo, Emilio Di; Didimo, Walter; Kaufmann, Michael; Liotta, Giuseppe
• Is Part Of: Information visualization. Volume 20:Number 1(2021)
• Page Start: 3
• Page End: 19
• Publication Date: 2021-01
• Subjects: Dynamic graph visualization -- drawing stability -- clustering visualization -- connected components -- arc diagrams -- orthogonal drawings; Information visualization -- Periodicals; 006.605
• DOI: 10.1177/1473871620972339
• Languages: English
• ISSNs: 1473-8716

Abstract

One of the primary goals of many systems for the visual analysis of dynamically changing networks is to maintain the stability of the drawing throughout the sequence of graph changes. We investigate the scenario where the changes are determined by a stream of events, each being either an edge addition or an edge removal. The visualization must be updated immediately after each new event is received. Our main goal is to provide the user with an intuitive visualization that highlights the different connected components of the graph while preserving the user's mental map after each event. The drawing stability is measured in terms of changes in the orthogonal relationships between vertices of two consecutive drawings. We describe two different visualization models, one for the 1-dimensional space and the other for the 2-dimensional space. In both models the connected components are drawn inside rectangular regions. To validate our approach, we report the results of an experimental analysis that compares the drawing stability of the online algorithm with that of an offline algorithm that knows in advance the whole sequence of events. We also present a case study of our online algorithm on a collaboration network.