Parallel Edge Splatting for Scalable Dynamic Graph Visualization - PDF

Please download to get full document.

View again

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Fan Fiction

Published:

Views: 5 | Pages: 9

Extension: PDF | Download: 0

Share
Related documents
Description
Parallel dge Splatting for Scalable ynamic Graph Visualization Michael urch, orinna Vehlow, Fabian eck, Stephan iehl, Member, I, and aniel Weiskopf, Member, I omputer Society Abstract We present a novel
Transcript
Parallel dge Splatting for Scalable ynamic Graph Visualization Michael urch, orinna Vehlow, Fabian eck, Stephan iehl, Member, I, and aniel Weiskopf, Member, I omputer Society Abstract We present a novel dynamic graph visualization technique based on node-link diagrams. The graphs are drawn side-byside from left to right as a sequence of narrow stripes that are placed perpendicular to the horizontal time line. The hierarchically organized vertices of the graphs are arranged on vertical, parallel lines that bound the stripes; directed edges connect these vertices from left to right. To address massive overplotting of edges in huge graphs, we employ a splatting approach that transforms the edges to a pixel-based scalar field. This field represents the edge densities in a scalable way and is depicted by non-linear color mapping. The visualization method is complemented by interaction techniques that support data exploration by aggregation, filtering, brushing, and selective data zooming. Furthermore, we formalize graph patterns so that they can be interactively highlighted on demand. A case study on software releases explores the evolution of call graphs extracted from the JUnit open source software project. In a second application, we demonstrate the scalability of our approach by applying it to a bibliography dataset containing more than 1.5 million paper titles from 60 years of research history producing a vast amount of relations between title words. Index Terms ynamic graph visualization, graph splatting, software visualization, software evolution. 1 INTROUTION Relationships among a set of objects are typically modeled as a graph consisting of a set of vertices and a set of edges that connect related vertices. Many of these relational datasets can be found in typical applications, not only limited to small datasets. For example, software systems may consist of hundreds or thousands of hierarchically organized classes connected by method calls and other dependencies, or digital libraries may include millions of papers linked by citations and keywords. A major challenge for the graph drawing community is the efficient and effective computation of graph layouts. There are some generally accepted aesthetic graph drawing criteria such as the minimization of edge crossings, the even distribution of nodes in the frame, or the uniformity of graph link lengths [9, 17]. Force-directed, orthogonal, or hierarchical layouts aim at optimizing a variety of these criteria. The temporal evolution of a graph introduces another interesting aspect to graph drawing but also comes along with further visualization challenges concerning the additional time dimension. The prevailing approach taken by graph drawing researchers is to use animation to represent the time dimension [10, 12]. This time-to-time mapping is intuitive but has some substantial drawbacks. The exploration of animated graph diagrams leads to high cognitive efforts due to our limited short term memory [1, 33]. For instance, it is difficult to observe trends over longer periods or to compare two non-subsequent time steps. Abrupt changes of the graph might furthermore destroy the viewer s mental image of the graph (mental map). Previous research investigated different dynamic graph visualization techniques that show the complete evolution at once in a single image instead of using animation [6, 7, 13, 14]. While these approaches largely prevent the problems of animated diagrams mentioned above, they come along with other problems [3]: due to the limited space that is left for a single graph when drawing all graphs of the sequence in a single diagram, scalability is hard to achieve especially with respect to the number of vertices. Michael urch, orinna Vehlow, and aniel Weiskopf are with VISUS, University of Stuttgart, Germany, -mail: {michael.burch, corinna.vehlow, Fabian eck and Stephan iehl are with the omputer Science epartment, University of Trier, Germany, -mail: {beckf, Manuscript received 31 March 2011; accepted 1 August 2011; posted online 23 October 2011; mailed on 14 October For information on obtaining reprints of this article, please send to: In this paper, we introduce a single-image visualization technique for exploring dynamic and hierarchically organized graphs, now focusing on scalability. We map each time step of the graph to a narrow rectangular area on screen. The vertices are arranged along the vertical borders of these areas, according to the order implied by the hierarchy. irected graph edges connect the vertices by straight links starting on the left hand side of the area and ending at the right hand side. In large graphs, this strategy leads to a plethora of overlapping edges. We tackle this problem by applying parallel edge splatting a technique that transforms the edges to a density scalar field by splatting those edges to the screen. Visualizing this field by color mapping allows us to recognize the trajectories of edges even in quite cluttered areas. The term parallel indicates the layout of graph vertices on parallel lines. Parallel edge splatting adopts the idea of density representation from graph splatting [34], yet is complementary because we splat edges instead of vertices. Our visualization tool provides several interactive features to manipulate and navigate dynamic graph data. With hierarchically structured graph vertices, expanding and collapsing of this hierarchy may be used to aggregate a certain number of nodes and their corresponding relations. The graph data can also be aggregated in the time dimension and filter functions can be applied to only display relations within a given weight interval. Pixel-based elements can be enlarged by a lens function. The tool design follows the information seeking mantra: overview first, zoom and filter, then details-on-demand [30]. Furthermore, we formalize graph patterns and provide functionality to interactively highlight these patterns. In two application scenarios, we demonstrate how the above combination of techniques increases the scalability of the single-image dynamic graph visualizations. First, we show the usefulness of our approach by a comprehensive case study on the evolution of the JUnit open source software system. Second, we analyze the evolution of title words occurring in more than 1.5 million paper titles acquired in the LP [25]. 2 RLAT WORK Visualizing dynamic relational data is a challenging task due to a number of visual dimensions to be represented in the same view: vertices, edges, and time. Node-link diagrams are effective for perceiving related objects and solving path-related tasks. However, graph datasets may reach sizes with which traditional graph layout algorithms cannot deal efficiently. A mapping of all edges of a dense graph to a 2 plane leads to visual clutter [29] caused by many edge crossings, even after applying sophisticated layout algorithms that take various aesthetic criteria for graph drawing into account [4, 37]. The time dimension is typically displayed by a natural time-to-time mapping in graph animation [10, 12]. omplex algorithms have to be applied to reduce the user s cognitive load, especially to preserve the user s mental map of the graph diagram over time. A recent state-of-the-art report by van Landesberger et al. [36] surveys existing research and challenges for visualizing large static and dynamic graphs. Instead of representing the time dimension in the graph data by animation, we map time to space and show the subsequent graphs in a static diagram. Our approach is inspired by the TimeArcTrees visualization [14], where graph nodes are arranged on vertical lines and directed edges are drawn as arcs. In TimeArcTrees, the size of each arc depends on the number of nodes that are located between source and target node, whereas the position of each arc (left or right hand side of the vertical axis) depends on whether the corresponding edge is an upward or downward edge. Visual clutter is reduced by optimizing the arrangement of the nodes. In contrast, the technique presented in this paper uses straight lines instead of arcs to represent the graph edges and splits vertices so that all edges point from left to right. Related to TimeArcTrees, the TimeRadarTrees [7] and the Time- SpiderTrees [14] approaches use a radial layout and draw each graph of the sequence in an annulus (ring). These single-image dynamic graph visualization techniques are limited to graphs consisting of a few dozens of vertices because each vertex consumes some space on a vertical line or a circumference of a circle. Another approach is to stack a sequence of node-link diagrams on top of each other such that the nodes representing the same vertex are aligned [6, 13]. This, however, increases the problem of clutter produced by overlapping visual artifacts. The visual representation produced by our technique is visually similar to parallel-coordinate plots [21]. While polylines in parallel coordinates typically span all coordinate axes, the lines in our approach represent graph edges and are contained within the drawing area of a single graph of the sequence. Therefore, the visual signatures and interpretation differ. Similar to the density model of parallel edge splatting, there are density-based variants of parallel-coordinate plots, e.g., [2, 5, 16, 22, 26, 38]. In particular, there are some splatting techniques for parallel coordinates [11, 15, 40]. Our approach is technically similar to splatting of parallel coordinates, but is based on discrete graph data; vertices are laid out on discrete positions on vertical lines and edges are discrete objects that cover a set of discrete points on the 2 plane. Furthermore, association rules for text mining can be visualized in a way that looks similar to our dynamic graph visualization technique: the elements are arranged on vertical lines; sequence rules connect these elements by straight lines from left to right on a timeline [39]. Van Liere and de Leeuw [34] introduced a graph splatting technique to transform graph data into a 2 scalar field, which is used as a basis to render a heatmap, a height field, or a set of contours. The main difference to our work is the fact that they only use the vertex information of the graph to generate a splat field. The relationship information on which our approach is built is not explicitly visualized. Holten and Van Wijk [20] used a force-directed edge bundling approach in which a pixel-based representation is applied to emphasize regions with many edges. A similar idea may also be applied to vertically arranged vertices [19]. Telea and rsoy use a combination of distance-based splatting and skeletonization to generate image-based edge bundles [32]. In contrast to our work, they focus on graphs that do not change over time, whereas we focus on time-varying directed graphs. We will discuss work related to our application scenarios in Section 5. 3 VISUALIZATION THNIQU Our visualization technique targets the problem of displaying dynamic weighted directed graphs in a single static view. We use parallel vertical axes to place the aligned graph vertices. The initial vertex position follows a predefined hierarchical order if there is any available. irected graph edges are visually encoded as direct links between two subsequent axes and are oriented from left to right. To overcome the problem of visual clutter in dense graphs, we apply splatting and antialiasing to the graph links, obtaining a scalable visualization. Time step after time step of the dynamic graph is arranged so that the user can perceive evolving graph structures. 3.1 ata Model We model a directed multi-graph in the graph-theoretic sense as G = (V, A ) where V denotes the set of vertices and A V V W denotes the set of directed adjacency edges that consists of ordered triples of elements. The first component denotes the start vertex, the second component the target vertex, and the third component W W a finite multi-set of positive real-valued numbers representing the corresponding multi-edge, i.e., the weights of the relations. Additionally, each graph vertex v V is hierarchically organized in a tree structure H = (V, I ) where V is the vertex set and I V V are the directed inclusion edges implied by the hierarchy such that (v,w) I iff v is the parent of w. A dynamic weighted directed multi-graph in an information hierarchy is modeled as a finite sequence of graphs Γ := {G 1,G 2,...,G n } where G i = (V i, Ai ), V i V, Ai A, 1 i n. We assume that the hierarchical organization of the graph vertices remains constant for all graphs in the sequence. 3.2 Graph Layout To illustrate the visual encoding of such dynamic graph data by parallel edge splatting, we start with a single static directed graph as shown in Figures 1 (a) and (b). The right part of Figure 1 (a) presents a possible layout of the adjacency information of the directed weighted graph embedded into the 2 plane. The small graph example consists of five nodes labeled A,,,, and. There are eight directed weighted edges, where the weights are visualized by color coding. One of the edges is a self-edge (at node ). The left part of Figure 1 (a) shows the hierarchical organization of the graph vertices as a traditional nodelink diagram. Figure 1 (b) illustrates the transformation of the graph data in Figure 1 (a) into our new layout. First, the graph nodes are mapped to a pair of parallel and vertically aligned lines; the mapping is identical for both lines. These lines build the axes for visually encoding the directed edges starting at the vertical position of the corresponding start node on the left axis and pointing to the vertical position of the corresponding target node on the right axis. To retain the information about the hierarchical organization of the graph nodes, we add an orthogonal node-link tree diagram in the left part of Figure 1 (b), where the tree nodes are vertically aligned with the corresponding graph nodes on the vertical axes. Initially, there is no special ordering of the graph nodes on the vertical axes. In our approach, we use the hierarchical organization to generate a total order of the nodes where the order of the subhierarchies in each level is not yet fixed. We use a depth-first traversal of the graph nodes and follow subhierarchies according to their order in memory. The nodes are placed equidistantly from top to bottom. If there is no hierarchy defined (e.g., for a graph without directly associated hierarchy), a hierarchy needs to be constructed in a preprocessing step, e.g., by employing hierarchical clustering of the graph nodes. Furthermore, nodes are not necessarily arranged on equidistant positions; if a metric is available to define node distances on the axis, non-uniform distances can be used. A dynamic graph is a graph that changes over time and can be modeled as a sequence of single graphs Γ = {G 1,G 2,...,G n }. Our technique is readily extended to apply it to evolving graph structures. For displaying n graphs of a sequence, we just need (n + 1) copies of the vertical axis and place these axes side-by-side. The space between two A A (a) (b) (c) A A A A Fig. 2. dge splatting is applied to help a viewer trace links even in dense graph regions. The leftmost subfigure shows a square to be discretized and enlarged in the center subfigure. The sum of weight coverage implied by adding each link weight is color-coded in the rightmost subfigure. olor coding is changed due to a new maximum value. time Fig. 1. A step-by-step visual encoding of dynamic directed and weighted graphs in an information hierarchy. (a) A single directed and weighted graph in a 2 layout. (b) The same graph data mapped to parallel vertical lines (1 layout). (c) A sequence of five directed and weighted graphs with an additional hierarchical organization of the nodes represented as a layered icicle plot. subsequent axes is used to display the graph edges of a single time stamp. The first graph is associated with the leftmost pair of axes; subsequent graphs follow to the right. Figure 1 (c) shows an example of a sequence of five graphs. The leftmost graph in the diagram is the example taken from Figure 1 (b). The hierarchical organization of the graph nodes can be obtained by inspecting the layered icicle plot [23] in the left part of Figure 1 (c). From our parallel edge graph layout, dynamic graph behavior can be readily analyzed by visual inspection. For example, Figure 1 (c) shows that node has a self-edge (with weight 2) throughout the sequence; edges from node to, from to A, and from A to are always present. 3.3 Splatting Technique Visualizing graphs in node-link diagrams may lead to many edge crossings and, hence, to visual clutter in the display. This phenomenon even occurs for graphs with a small number of vertices. Traditional graph layout algorithms become very time-consuming due to their high computational complexity, already for a dense graph with just a few hundred vertices. Furthermore, even sophisticated layout techniques may generate unsatisfying results in many situations. The visualization of an additional time dimension and an additional hierarchical organization is a challenging task for these layout approaches. As discussed before, we represent time-varying graphs by a 1 layout of the nodes and a time-to-space mapping of the dynamics. A drawback of restricting the layout of graph nodes to 1 is a further increase of visual clutter caused by many edge crossings. Therefore, a graph drawing method for dense coverage by edges is crucial. We follow the general strategy of transforming plots with opaque plotting elements (i.e., lines in our case) to corresponding density plots. In our case, graph edges are transformed to density distributions. We adopt a splatting approach, projecting the density representation of the edges to image space. The basic splatting algorithm has only little graphics requirements. First, it needs a framebuffer or similar storage for the density image. Just a single value needs to be stored per pixel in the framebuffer. The number representation of such a pixel value should be chosen to capture the dynamic range of densities. Typically, somewhere between (a) Fig. 3. Visualization of a real-world dynamic graph with homogeneous edge weights (only a detail of the visualization shown) without (a) and with edge splatting (b). 16-bit fixed-point to 32-bit floating-point number format is appropriate. Furthermore, the framebuffer has to have support for additive blending, i.e., the plus operator according to Porter and uff [28]. As second requirement, the splatting algorithm needs a line rasterization method that is capable of rendering lines of a specified intensity to the framebuffer. Any of today s typical graphics systems meets these requirements easily, regardless of whether it is graphics hardware run by low-level graphics API (OpenGL or irectx) or whether it is a highlevel software API, such as the Java S Runtime nvironment used in our case. With these graphics components, the basic splatting algorithm works as illustrated in Figure 2. Here, we only consider one pair of vertical axes; further time steps are included by applying the splatting algorithm time-after-time at subsequent axes pairs. The rendering algorithm visits all graph edges and rasterizes their line representations. The weights of the edges determine the line intensity. Additive blending is enabled throughout the rendering process. Since additive blending is commutative, the edges can be rendered in arbitrary order. At the end of the basic splatting process, the framebuffer contains the 2 image of the edge densities. Figure 3 demonstrates the effect of this edge splatting approach. Since the density image may contain densities with high dynamic range, a postprocessing stage is recommended. Here, some data mapping is computed to reduce the dynamic range. We recommend a logarit
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks