Seeing more than the graph: evaluation of multivariate graph visualization methods.

Many real-world networks are multivariate, i.e., they have attributes associated with nodes and/or edges. Examples include social networks whose nodes represent people and edges represent relationships. There is usually information about each person (such as name, age, and gender) and the relationship (such type, duration, and strength). Besides common graph analysis tasks (such as identifying the most influential or structurally important nodes), there are more complex analyses for multivariate networks. One of these is the multivariate graph clustering, i.e., identifying clusters formed by nodes that have similar attributes and are close to each other in terms of graph distance. For instance, in social network analysis, it is interesting to sociologists whether or not people with similar characteristics (node attributes) are also connected to each other. Currently there are very few visualization methods available for such analysis.
Graph and multivariate visualization have been well studied separately in the literature. Herman et al. summarized the recent work on graph visualization [3], and Wong and Bergeron covered the development in multivariate visualization [4]. However, there is relatively less work available on multivariate network visualization. Two types of approaches are commonly used. The first one is the mapping approach, which maps attributes to visual elements of a node or edge. A simple example is to map one attribute to node size and another to node color [2]. A more advanced mapping approach uses glyphs to represent node or edge attributes. One such example is to use the length and width of a rectangle node glyph to represent two node attributes [1]. The second one is the 2.5D approach: it uses the third dimension to present the multivariate information, while the graph is shown on a 2D plane. Examples include the recently proposed "GraphScape" [5], which adopts a landscape metaphor: each attribute is represented by a two-and-a-half- dimensional surface, whose height indicates its value.
Each approach has its strength and weakness. The mapping approach is effective of showing numerical value using visual element such as size, but it can be difficult to compare the value of attributes represented by different elements such as size and color. The problem is alleviated by a carefully designed glyph, but visual complexity increases quickly as the number of attributes that a glyph needs to represent grows. The 2.5D approach is good at showing the distribution of attribute values over the network, but the attribute surface could introduce occlusion and affect the visibility of underlying network.
In this paper, we present a study evaluating the effectiveness of these two approaches for different analysis tasks. We compare the performance of mapping and 2.5D approach in a controlled lab environment. We included both simple tasks (such as identifying nodes with the largest attribute value) and complex tasks (such as multivariate graph clustering). The performance is measured both in terms of accuracy and completion time. The results indicate that statistically mapping approach performs better for the simple tasks, while the 2.5D approach is favored in the complex task. The outcomes from this study provide some guidelines for the design of effective multivariate graph visualization for different analysis tasks.

International Working Conference in cooperation with ACM-SIGCHI, ACM-SIGMM, SIGCHI Italy held in May 25-29, 2010 - Roma, Italy