Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Clustered graphs are graphs with recursive clustering structures over the vertices. This type of structure appears in many systems. Examples include CASE tools, management information systems, VLSI design tools, and reverse engineering systems. Existing layout algorithms represent the clustering structure as recursively nested regions in the plane. However, as the structure becomes more and more complex, two dimensional plane representations tend to be insufficient. In this paper, firstly, we describe some two dimensional plane drawing algorithms for clustered graphs; then we show how to extend two dimensional plane drawings to three dimensional multilevel drawings. We consider two conventions: straight-line convex drawings and orthogonal rectangular drawings; and we show some examples. <s> BIB001 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> From the Publisher: ::: This book is designed to describe fundamental algorithmic techniques for constructing drawings of graphs. Suitable as a book or reference manual, its chapters offer an accurate, accessible reflection of the rapidly expanding field of graph drawing. <s> BIB002 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Many networks under study in information visualization are "small world" networks. These networks first appeared in the study of social networks and were shown to be relevant models in other application domains such as software reverse engineering and biology. Furthermore, many of these networks actually have a multiscale nature: they can be viewed as a network of groups that are themselves small world networks. We describe a metric that has been designed in order to identify the weakest edges in a small world network leading to an easy and low cost filtering procedure that breaks up a graph into smaller and highly connected components. We show how this metric can be exploited through an interactive navigation of the network based on semantic zooming. Once the network is decomposed into a hierarchy of sub-networks, a user can easily find groups and subgroups of actors and understand their dynamics. <s> BIB003 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> We present Growing Polygons, a novel visualization technique for the graphical representation of causal relations and information flow in a system of interacting processes. Using this method, individual processes are displayed as partitioned polygons with color-coded segments showing dependencies to other processes. The entire visualization is also animated to communicate the dynamic execution of the system to the user. The results from a comparative user study of the method show that the Growing Polygons technique is significantly more efficient than the traditional Hasse diagram visualization for analysis tasks related to deducing information flow in a system for both small and large executions. Furthermore, our findings indicate that the correctness when solving causality tasks is significantly improved using our method. In addition, the subjective ratings of the users rank the method as superior in all regards, including usability, efficiency, and enjoyability. <s> BIB004 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Most analysts start with an overview of the data before gradually refining their view to be more focused and detailed. Multiscale pan-and-zoom systems are effective because they directly support this approach. However, generating abstract overviews of large data sets is difficult and most systems take advantage of only one type of abstraction: visual abstraction. Furthermore, these existing systems limit the analyst to a single zooming path on their data and thus to a single set of abstract views. This paper presents: 1) a formalism for describing multiscale visualizations of data cubes with both data and visual abstraction and 2) a method for independently zooming along one or more dimensions by traversing a zoom graph with nodes at different levels of detail. As an example of how to design multiscale visualizations using our system, we describe four design patterns using our formalism. These design patterns show the effectiveness of multiscale visualization of general relational databases. <s> BIB005 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> The research by the information visualization community (“Info Viz”) shows clearly that using a visual representation of data-sets enables faster analysis by the end users. Several scientific reasons explain these results. First of all, the visual perception system is the most powerful of all the human perception systems. In the human brain, 70% of the receptors and 40% of the cortex are used for the vision process [27,34]. Furthermore, human beings are better at “recognition” tasks than at “memorization” tasks [10]. This implies that textual representations are less efficient than visual metaphors when one wants to analyze huge data-sets. This comes from the fact that reading is both a memorization task and a recognition task. <s> BIB006 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Graph drawing is a basic visualization tool that works well for graphs having up to hundreds of nodes and edges. At greater scale, data density and occlusion problems often negate its effectiveness. Conventional pan-and-zoom, multiscale, and geometric fisheye views are not fully satisfactory solutions to this problem. As an alternative, we propose a topological zooming method. It precomputes a hierarchy of coarsened graphs that are combined on-the-fly into renderings, with the level of detail dependent on distance from one or more foci. A related geometric distortion method yields constant information density displays from these renderings. <s> BIB007 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> A compound graph is a frequently encountered type of data set. Relations are given between items, and a hierarchy is defined on the items as well. We present a new method for visualizing such compound graphs. Our approach is based on visually bundling the adjacency edges, i.e., non-hierarchical edges, together. We realize this as follows. We assume that the hierarchy is shown via a standard tree visualization method. Next, we bend each adjacency edge, modeled as a B-spline curve, toward the polyline defined by the path via the inclusion edges from one node to another. This hierarchical bundling reduces visual clutter and also visualizes implicit adjacency edges between parent nodes that are the result of explicit adjacency edges between their respective child nodes. Furthermore, hierarchical edge bundling is a generic method which can be used in conjunction with existing tree visualization techniques. We illustrate our technique by providing example visualizations and discuss the results based on an informal evaluation provided by potential users of such visualizations <s> BIB008 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> We describe ASK-GraphView, a node-link-based graph visualization system that allows clustering and interactive navigation of large graphs, ranging in size up to 16 million edges. The system uses a scalable architecture and a series of increasingly sophisticated clustering algorithms to construct a hierarchy on an arbitrary, weighted undirected input graph. By lowering the interactivity requirements we can scale to substantially bigger graphs. The user is allowed to navigate this hierarchy in a top down manner by interactively expanding individual clusters. ASK-GraphView also provides facilities for filtering and coloring, annotation and cluster labeling <s> BIB009 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> This paper introduces PivotGraph, a software tool that uses a new technique for visualizing and analyzing graph structures. The technique is designed specifically for graphs that are "multivariate," i.e., where each node is associated with several attributes. Unlike visualizations which emphasize global graph topology, PivotGraph uses a simple grid-based approach to focus on the relationship between node attributes and connections. The interaction technique is derived from an analogy with methods seen in spreadsheet pivot tables and in online analytical processing (OLAP). Finally, several examples are presented in which PivotGraph was applied to real-world data sets. <s> BIB010 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> The need to visualize large social networks is growing as hardware capabilities make analyzing large networks feasible and many new data sets become available. Unfortunately, the visualizations in existing systems do not satisfactorily resolve the basic dilemma of being readable both for the global structure of the network and also for detailed analysis of local communities. To address this problem, we present NodeTrix, a hybrid representation for networks that combines the advantages of two traditional representations: node-link diagrams are used to show the global structure of a network, while arbitrary portions of the network can be shown as adjacency matrices to better support the analysis of communities. A key contribution is a set of interaction techniques. These allow analysts to create a NodeTrix visualization by dragging selections to and from node-link and matrix forms, and to flexibly manipulate the NodeTrix representation to explore the dataset and create meaningful summary visualizations of their findings. Finally, we present a case study applying NodeTrix to the analysis of the InfoVis 2004 coauthorship dataset to illustrate the capabilities of NodeTrix as both an exploration tool and an effective means of communicating results. <s> BIB011 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> We present CiteWiz, an extensible framework for visualization of scientific citation networks. The system is based on a taxonomy of citation database usage for researchers, and provides a timeline visualization for overviews and an influence visualization for detailed views. The timeline displays the general chronology and importance of authors and articles in a citation database, whereas the influence visualization is implemented using the Growing Polygons technique, suitably modified to the context of browsing citation data. Using the latter technique, hierarchies of articles with potentially very long citation chains can be graphically represented. The visualization is augmented with mechanisms for parent-child visualization and suitable interaction techniques for interacting with the view hierarchy and the individual articles in the dataset. We also provide an interactive concept map for keywords and co-authorship using a basic force-directed graph layout scheme. A formal user study indicates that CiteWiz is significantly more efficient than traditional database interfaces for high-level analysis tasks relating to influence and overviews, and equally efficient for low-level tasks such as finding a paper and correlating bibliographical data. <s> BIB012 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Supporting visual analytics of multiple large-scale multidimensional data sets requires a high degree of interactivity and user control beyond the conventional challenges of visualizing such data sets. We present the DataMeadow, a visual canvas providing rich interaction for constructing visual queries using graphical set representations called DataRoses. A DataRose is essentially a starplot of selected columns in a data set displayed as multivariate visualizations with dynamic query sliders integrated into each axis. The purpose of the DataMeadow is to allow users to create advanced visual queries by iteratively selecting and filtering into the multidimensional data. Furthermore, the canvas provides a clear history of the analysis that can be annotated to facilitate dissemination of analytical results to stakeholders. A powerful direct manipulation interface allows for selection, filtering, and creation of sets, subsets, and data dependencies. We have evaluated our system using a qualitative expert review involving two visualization researchers. Results from this review are favorable for the new method. <s> BIB013 </s> Hierarchical Aggregation for Information Visualization: Overview, Techniques, and Design Guidelines <s> Node-Link Diagrams <s> Many graph visualization systems use graph hierarchies to organize a large input graph into logical components. These approaches detect features globally in the data and place these features inside levels of a hierarchy. However, this feature detection is a global process and does not consider nodes of the graph near a feature of interest. TugGraph is a system for exploring paths and proximity around nodes and subgraphs in a graph. The approach modifies a pre-existing hierarchy in order to see how a node or subgraph of interest extends out into the larger graph. It is guaranteed to create path-preserving hierarchies, so that the abstraction shown is meaningful with respect to the structure of the graph. The system works well on graphs of hundreds of thousands of nodes and millions of edges. TugGraph is able to present views of this proximal information in the context of the entire graph in seconds, and does not require a layout of the full graph as input. <s> BIB014
Node-link diagrams are perhaps the most straightforward graph visualizations, drawing a graph as a collection of visual nodes arranged on a two-dimensional or threedimensional visual substrate using some graph layout algorithm BIB002 and connected using visual links. However, large numbers of edges or nodes may cause a highly congested visualization despite the use of efficient layout algorithms, prompting the need for hierarchical aggregation BIB001 , either on edges, nodes, or both. For node-link diagrams (as opposed to matrix visualizations, see below), edge aggregation is the least common of these approaches and only a few techniques take this route. Hierarchical edge bundles BIB008 group links together into thick bundles, akin to how electrical or network wires are tied together to avoid excessive tangling. However, despite its name, this is not strictly a hierarchical visualization technique because the aggregation is performed in visual space using implicit curves and not in data space. As for node aggregation, there are essentially two approaches to conducting hierarchical aggregation on graphs visualized using node-link diagrams: top-down or bottom-up. In the bottom-up approach, a layout is computed for the whole graph, and the nodes are, then, hierarchically grouped using geometrical means BIB007 . However, by requiring a complete graph layout prior to aggregation, this approach may not scale well to extremely large graphs. In the top-down approach, on the other hand, we, instead, start with a hierarchical aggregation and use this to dynamically compute layout as the user is drilling down into the data set. This strategy is used by the TugGraph BIB014 system. Because this approach does not require an expensive global graph layout but, instead, amortizes this cost online as the user is exploring, it scales better than bottom-up approaches. It is, therefore, more promising for future work on aggregating large-scale graphs. In general, Auber et al. BIB003 show how to use hierarchical node clustering for node-link diagrams to turn a graph into a multiscale structure based on its small-world structure. Their Tulip BIB006 system uses metanodes to cluster several nodes into a visual aggregate hierarchy. Metanodes may have a standard node visual representation with the union of all incoming and outgoing edges of the aggregated subnodes, or they may also show simplified contents, such as the clustered small-world network as miniature thumbnails for each node. Building on the previous work, Archambault  presents a feature-based approach to visualizing graphs using nodelink diagrams, and discusses a range of graph drawing techniques for this purpose. These techniques are designed to draw hierarchical representations of graphs; some of the proposed techniques support local aggregation control using distinct visual aggregates for metanodes such as nested circles (open) and hexagons (closed). The work also presents many specializations of the general principles introduced in this paper that are specific to graphs and node-link diagrams; thus, this is a good example of how to adapt hierarchical aggregation to a specific subdomain. ASK-GraphView BIB009 combines clustering functionality with navigation in hierarchically aggregated node-link diagrams of large-scale externalized graphs. The system supports interactive expansion and collapse of aggregate branches in an unbalanced fashion, and also manages visual clutter through transparency and masking of edges, similar to the interaction techniques cataloged in this paper.  . Histograms for each axis show the distribution of data points. Fig. 11 . Color histogram representation of a multidimensional university student data set in a starglyph visualization from the DataMeadow BIB013 ,  . Brightness indicates high density. The NodeTrix BIB011 technique combines node-link diagrams with adjacency matrices for representing communities in social networks. This method utilizes a fixed twolevel aggregation where subsets of a graph are clustered and rendered as adjacency matrices connected to other matrices using edge bundles similar to Holten's hierarchical edge bundles BIB008 . Because the aggregation is fixed, however, many of the interaction techniques described in Section 3.5 do not make sense for NodeTrix visualizations. In an extension BIB012 of the growing polygons BIB004 dependency visualization, Elmqvist and Tsigas show how to augment the technique with hierarchical subsets that group together nodes in a directed acyclic graph. Their visual aggregate representation shows the cumulative dependencies for each subset, and additionally adds a drop-shadow to indicate that the subsets can be expanded (Fig. 13) . Finally, pivot graphs BIB010 exploit data cube aggregation BIB005 to roll up nodes into metanodes based on attribute values for categorical data. A specialization of hierarchical aggregation, this allows for the creation of simplified nodelink graphs showing primarily the counts of aggregated nodes and edges. However, because the aggregation, again, is not hierarchical in nature, the interaction techniques described in this paper do not apply to pivot graphs.