The EDGE Project

(Evolving and Dynamic Graph Evaluation)

Dr Helen C. Purchase

EPSRC Funded Grant number EP/DO77982

Research Assistant: Dr Peter Saffrey

This project will look at the effectiveness of dynamic information visualisation systems, particularly in the area of evolving graph layout. It will last one year, starting September 2006, and will entail the design of novel experiments to investigate various factors of existing dynamic graph layout algorithms.

A more detailed description of the project is provided below. Any questions can be addressed to Helen Purchase

Research Problem

The problem to be addressed is that existing systems that display dynamically changing graph structures have not been empirically investigated with respect to human understanding. Their design has been typically based on intuition and ad-hoc assumptions.

Dynamic visualisation systems that present changing information in a manner that makes the information easy to understand and use will assist users in efficient and effective completion of their task. A good display of changing relational information can be an indispensable aid to understanding; a poor display can confuse or mislead.

In building dynamic graph layout systems, algorithm designers make design decisions that alter the way in which the dynamic changes are displayed: these design decisions are here called ‘principles’.  A principle may be represented by a value range for a parameter (for example, the maximum distance a node may move between time-slices), or as an unalterable decision (for example, the static layout algorithm used at each time-slice). Not only has no work been performed on identifying relevant principles for dynamic graph layout, no human empirical work has been undertaken to investigate the effect of these different principles on human understanding.

Existing dynamic graph layout systems tend to provide a ‘one algorithm fits all’ solution to the problem of displaying dynamic graphs, not taking into account the domain of use, and the purposes for which users need the visualisation. It may be the case, for example, that the best principles for the display of a changing web site may not be the best principles for an evolving family tree: we do not know, as this issue has never been investigated.

This project will enable the first experiments on existing dynamic graph layout systems to be designed and conducted. Investigating these systems will allow us to advise both designers of new dynamic graph drawing systems as to the most appropriate design for human understanding, and users of existing systems as to the most appropriate system parameters to use according to their purpose. In addition, the results will provide useful feedback to the researchers who have implemented the existing systems, who either do not have the experience or the time to perform such studies themselves.

Now that there are several feasible and efficient dynamic graph layout systems available, the next logical step is to perform empirical studies on their use. This is a previously unexplored field, and raises interesting experimental challenges not present in the prior studies on static graph drawings. The ability of dynamic graphs to depict a large quantity of information over time makes them very different from static graphs where all the information is presented at once.

This project will therefore:

• identify appropriate existing dynamic graph drawing systems, and seek assistance from the authors in understanding the tool’s layout principles, and potentially their support in instrumentation of the software;
• investigate these systems to define important and interesting principles for investigation; define these principles clearly, and state them in terms of experimental conditions;
• define an appropriate experimental methodology for dynamic graph layout algorithms, including investigating the most appropriate experimental  tasks and developing an experimental framework for studies of this kind;
• perform experiments according to this methodology, using both abstract graphs (i.e. embodying no meaning), and graphs with semantic content. This will be an iterative process, as the methodology will need to be adapted for different domains and different conditions.

The Experiments

The first two studies looked at syntactic dynamic graphs - node-edge drawings that change over time and which are not semantically related to any domain. Two different dynamic layout algorithms were studied, first with a small graph, and then with a larger one. The tasks were highest degree and shortest path questions. [Experimental materials]

Publications

[1] Purchase H.C., Hoggan E. and Görg C. How Important is the "Mental Map"? - an Empirical Investigation of a Dynamic Graph Layout Algorithm. Proceedings of the Graph Drawing Conference, Karlsruhe, Germany, September 2006. [Experimental Graphs]

[2] Saffrey P and Purchase, H.C. The "Mental Map" versus "Static Aesthetic" Compromise in Dynamic Graphs: A User Study. [Experimental Graphs]

[3] Purchase, H.C. and Samra, A. Extremes are better: investigating mental map preservation. [Experimental Graphs]