On the Application of Experimental Results in Dynamic Graph Drawing

Abstract

A number of experiments have looked at various factors when visualizing dynamic graphs. Animation, small multiples, drawing stability (also known as the mental map) have been investigated. In this paper, we examine these results from the perspective of presentation method| mainly animation and small multiples. We also present ndings of recent empirical studies on drawing stability and how these results interact with these presentations methods. Finally, we discuss the challenges of applying these results in various application areas.

Keywords

• Empirical Studies
• Dynamic Graph Drawing
• Applications

Introduction

Dynamic data visualization and more speci cally dynamic graph drawing has been very active over the past few years with the development of many visualization tools and algorithms as well as empirical studies to test the e ectiveness of such approaches with users [ 5, 7 ]. The most common techniques for visualizing dynamic graphs is via node-link representations where nodes and edges in the graph can be added or removed evolving the graph over time. When visualizing dynamic graphs in this way, we need to consider a variety of parameters when presenting the data. We might present the data using an interactive animation that evolves the time series by fading in/out graph elements from the display. Another alternative is a small multiples presentation of the data that allows a series of timeslices to presented on the screen at once.

Independent of the choice of visualization method, dynamic node-link representations need to consider drawing stability|known more often as preserving the mental map [ 9, 13 ] in the dynamic graph drawing literature. As the mental map or cognitive map in psychology corresponds to the internal representation of the data inside the human mind, we advocate the use of the term drawing stability. Drawing stability would exclude the perception of the dynamic graph by the human and refers solely to the positions of the nodes in the external representation of the dynamic graph (usually the computer screen).

In this paper, we begin by presenting empirical results in other elds that have performed human-centred experiments on the visualization of dynamic data. Using this discussion as a basis, we demonstrate that the results of recent humancomputer interaction experiments that have tested e ectiveness of interactive animation and small multiples for the visualization of dynamic node-link representations are consistent with this literature. We then expand on our previous work [ 3 ] and discuss how these concepts interact with drawing stability. Finally, we discuss the challenges in applying these results to wider application areas. 2

Animation and Small Multiples

Animation and small multiples are two common methods for visualizing dynamic data sets. When we say animation in this paper, we mean interactive animation whereby the user of the visualization has complete control over the evolution of the dynamic data. This presentation method is an interactive movie where the current frame is given to the entire screen and smooth transitions between frames demonstrate how the data evolves. A small multiples [ 15 ] presentation of the data places a series of snapshots side-by-side on the screen simultaneously and the user scans these windows to perceive temporal evolution. In the terminology of Bach et al. [ 5 ], animation is interactive time cutting and small multiples is a type of time juxtaposing.

Tversky et al. [ 16 ] performed a survey of experiments in psychology, education, and a variety of other elds. The survey did not nd convincing empirical evidence that animation assisted with tasks in these elds. Where animations seemed to perform well, they often took time to comprehend so they do have a cost in terms of human performance.

Despite this strong evidence against animation as a presentation method in this survey, the authors concede there are certain circumstances when animation can be useful. Speci cally, animated transitions can be helpful if there are complex reorientations of the data. The paper even concludes its review of empirical studies on animation with the following caveat: { \At this point then, the most promising uses of animation seem to be to convey real-time changes and reorientations in time and space." [ 16 ] Evidence also exists that animations can be used e ectively for highlighting. Ware and Bobrow [ 17 ] demonstrate that animations can be use to highlight subgraphs within a larger graph. Gri en et al. [ 12 ] show that animation can be used to highlight clusters of hexagons against a similarly coloured eld of distractors hexagons when compared to a small multiples representation.

This body of evidence suggests that animation is important in speci c circumstances: to support reorientations in time/space and highlighting. Outside of these circumstances, animations often have a cost|speci cally in the time that it takes to use them. This evidence suggests that static images, with time encoded spatially, for the visualization of dynamic data should be encouraged. 2.1

Animation, Small Multiples, and Dynamic Graphs Human-centred experiments testing the e ectiveness of interactive animation and small multiples in dynamic graph drawing seems to show the same result| namely, that interactive animations, although comprehensible, have a cost in terms of the time that it takes to use them. Archambault et al. [ 4 ] provide evidence that small multiples is signi cantly faster than interactive animation for all tasks tested and with no di erence in error rate for three of them. Farrugia and Quigley [ 10 ], in a social networking scenario, nd that a small multiples representation is faster with no signi cant di erence in error rate. Therefore, these experiments provide evidence that interactive animations have a cost in terms of the time it takes to use them, providing further support for the ndings of Tversky et al. [ 16 ] in the area of dynamic graph visualization.

However, used in moderation, animation can help in speci c circumstances| in particular, with respect to highlighting [ 17, 12 ]. Archambault et al. [ 4 ] found that interactive animation, when compared to small multiples, helped reduce error rates when trying to determine the number of times a node or edge was added to a dynamic graph series. Animation may have assisted in highlighting the nodes and edges in the experiment. There is some evidence that animation may help make graph sequences more memorable [ 8, 1 ]. Animation may have played a role in highlighting graph elements, improving memorability.

Tversky et al. [ 16 ], as quoted in the previous section, stated that animation could be useful in supporting reorientations in time and space. Although there is no evidence available when comparing interactive animation to small multiples directly, when comparing no transitions to both staged and linear transitions for dynamic graphs, animation can help [ 8, 14, 6 ] for full screen and hybrid visualizations of dynamic graphs. A possible reason for these ndings is that if there are signi cant reorientations of the graph between adjacent timeslices, interactive animation helps disambiguate the identities of nodes and edges in the graph when their positions change extensively.

Animations of dynamic graphs can help in clarifying spatial reorientations and in highlighting. However, often these advantages come at a cost in terms of the time that it takes to use them. Thus, for dynamic graph visualization, we would encourage further work on small multiples and other approaches where time is represented spatially. Very short animations for highlighting or clarifying critical spatial reorientations are probably the most e ective uses of animation. 3

What About Drawing Stability?

A survey [ 3 ] of experimental results in dynamic graph drawing prior to 2012 could not nd evidence that drawing stability [ 13, 9 ] helps when visualizing undirected dynamic graphs. The survey concludes that drawing stability may not be as useful as originally thought and that further study was needed. Two subsequent studies have found that drawing stability can help in certain circumstances.

Ghani et al. [ 11 ] demonstrate that, when comparing dynamic drawings with pinned vertices to drawing each time period independently, drawing stability can help users perceive the order of addition/removal of nodes from a graph. Archambault and Purchase [ 2 ] provided evidence that dynamic graph drawing algorithms which support drawing stability help when the tasks are maplike|such as locating nodes or following long paths through the graph. This experiment su ciently challenged the participant by requiring a high number of pertinent nodes ( ve or greater) to the question and by not highlighting these nodes via any other means (e.g. colour). A stable external representation of the dynamic graph was helpful under these conditions.

Drawing stability is helpful for locating speci c nodes in a visualization or following long paths|tasks that are similar to nding our way on a map. One could view drawing stability as a form of spatial highlighting where position is used to identify nodes. In situations where the drawing cannot be kept stable, animated transitions could still be helpful. However, we would encourage that the animations used to clarify these reorentations be short in duration to minimize their temporal cost. 4

Challenges in Application of Results

A number of challenges exist in applying these experimental results to application areas of dynamic graph drawing.

In human-centred experiments in this area, the number of nodes and edges used in the experimental stimuli is small. In many cases, results on small graphs can be generalized to large graphs as aggregation and ltering are frequently used to reduce the nodes and edges to a reasonable number for visualization. However, further investigation into methods to visualize very large dynamic graphs directly can be fruitful, and experiments can assist in validating these techniques.

The time series used in experiments conducted so far is of short duration. If aggregation or ltering is applied along the temporal dimension, the results of these experiments can be applied directly. Development of techniques based on aggregation and ltering along the temporal dimension have begun with systems such as Di Ani [ 14 ] and GraphDiaries [ 6 ]. However, we would encourage further investigation into methods for the direct visualization dynamic graphs with long time series.

Further development of novel interaction methods with dynamic graphs is needed. Interactive animation often has a cost in terms of user time, but it is only one form of interaction with dynamic graphs. The development of novel and e ective interaction methods would greatly bene t this area.

When designing human-centred experiments, we need to be careful that the chosen tasks are appropriate and realistic. Often, the best way to ensure this realism is to base the chosen experimental tasks on applied research. Secondly, it is very important for us as a community to become familiar with relevant experiments conducted in psychology and perception. Experiments in these communities are often related and relevant to the tools we design.

This paper focuses on formal, human-centred experiments in dynamic graph drawing and reports on new results in the area. Secondly, it provides some ideas on the application of these results. We suggest that similar evaluation methodologies could be used more widely to inform the design and development of dynamic graph drawing methods in other domains.

References

1. D. Archambault and H. C. Purchase . The mental map and memorability in dynamic graphs . In Proc. of the IEEE Paci c Visualization Symposium (Paci cVis '12) , pages 89 { 96 , 2012 .

2. D. Archambault and H. C. Purchase . Mental map preservation helps user orientation in dynamic graphs . In Proc. of Graph Drawing (GD '12) , pages 475 { 486 , 2012 .

3. D. Archambault and H. C. Purchase. The "map" in the mental map: Experimental results in dynamic graph drawing . Int. J. of Human-Computer Studies , 71 ( 11 ): 1044 { 1055 , 2013 .

4. D. Archambault , H. C. Purchase , and B. Pinaud . Animation, small multiples, and the e ect of mental map preservation in dynamic graphs . IEEE Trans. on Visualization and Computer Graphics , 17 ( 4 ): 539 { 552 , 2011 .

5. B. Bach , P. Dragicevic , D. Archambault , C. Hurter , and S. Carpendale . A review of temporal data visualizations based on space-time cube operations . In EuroVis 2014 { State of the Art Reports , 2014 .

6. B. Bach , J.-D. Fekete , and E. Pietriga. GraphDiaries: Animated transitions and temporal navigation for dynamic networks . IEEE Transactions on Visualization and Computer Graphics , 20 ( 5 ): 740 { 754 , 2014 .

7. F. Beck , M. Burch , S. Diehl , and D. Weiskopf . The state of the art in visualizing dynamic graphs . In EuroVis 2014 { State of the Art Reports , 2014 .

8. B. B. Bederson and A. Boltman . Does animation help users build mental maps of spatial information? In Proc. of the 1999 IEEE Symposium on Information Visualization , pages 28 { 35 , 1999 .

9. M. K. Coleman and D. S. Parker . Aesthetics-based graph layout for human consumption . Software - Practice and Experience , 26 ( 12 ): 1415 { 1438 , 1996 .

10. M. Farrugia and A. Quigley . E ective temporal graph layout: A comparative study of animation versus static display methods . Journal of Information Visualization , 10 ( 1 ): 47 { 64 , 2011 .

11. S. Ghani , N. Elmqvist , and J. S. Yi . Perception of animated node-link diagrams for dynamic graphs . Computer Graphics Forum , 31 ( 3 ): 1205 { 1214 , 2012 .

12. A. L. Gri en , A. M. MacEachren , F. Hardisty , E. Steiner, and B. Li . A comparison of animated maps with static small-multiple maps for visually identifying spacetime clusters . Annals of the Association of American Geographers , 96 ( 4 ): 740 { 753 , 2006 .

13. K. Misue , P. Eades , W. Lai , and K. Sugiyama . Layout adjustment and the mental map . Journal of Visual Languages and Computing , 6 : 183 { 210 , 1995 .

14. S. Ru ange and M. J. McGu n. Di Ani : Visualizing dynamic graphs with a hybrid of di erence maps and animation . IEEE Transactions on Visualization and Computer Graphics , 19 ( 12 ): 2556 { 2565 , 2013 .

15. E. Tufte. Envisioning Information . Graphics Press, 1990 .

16. B. Tversky , J. Morrison , and M. Betrancourt . Animation: Can it facilitate? Int. Journal of Human-Computer Studies , 57 ( 4 ): 247 { 262 , 2002 .

17. C. Ware and R. Bobrow . Supporting visual queries on medium sized node-link diagrams . Journal of Information Visualization , 4 ( 1 ): 49 { 58 , 2005 .