A Survey of Multi-faceted Graph Visualization - PDF

Please download to get full document.

View again

of 16
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:

Genealogy

Published:

Views: 8 | Pages: 16

Extension: PDF | Download: 0

Share
Related documents
Description
Eurographics Conference on Visualization (EuroVis) (2015) R. Borgo, F. Ganovelli, and I. Viola (Editors) STAR State of The Art Report A Survey of Multi-faceted Graph Visualization Steffen Hadlak 1, Heidrun
Transcript
Eurographics Conference on Visualization (EuroVis) (2015) R. Borgo, F. Ganovelli, and I. Viola (Editors) STAR State of The Art Report A Survey of Multi-faceted Graph Visualization Steffen Hadlak 1, Heidrun Schumann 2, and Hans-Jörg Schulz 1 1 Fraunhofer IGD Rostock, Germany 2 University of Rostock, Germany Abstract Graph visualization is an important field in information visualization that is centered on the graphical display of graph-structured data. Yet real world data is rarely just graph-structured, but instead exhibits multiple facets, such as multivariate attributes, or spatial and temporal frames of reference. In an effort to display different facets of a graph, such a wealth of visualization techniques has been developed in the past that current surveys focus on a single additional facet only in order to enumerate and classify them. This report builds on existing graph visualization surveys for the four common facets of partitions, attributes, time, and space. It contributes a generic high-level categorization of faceted graph visualization that subsumes the existing classifications, which can be understood as facet-specific refinements of the resulting categories. Furthermore, it extends beyond existing surveys by applying the same categorization to graph visualizations with multiple facets. For each of the introduced categories and considered facets, this overview provides visualization examples to illustrate instances of their realization. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Picture/Image Generation Line and curve generation 1. Introduction Data often combines various aspects, such as spatial and temporal frames of reference, or multiple attribute values per data item. We term such data multi-faceted in accordance with Kehrer and Hauser, who introduced this term to describe this characteristic for scientific data [KH13]. The importance and interplay of data facets are reflected in tailored visualization techniques for multi-faceted data. In this report, we provide an overview of visualizations specifically tailored to multi-faceted graph-structured data. All visualizations for graph-structured data have in common that they encode in some form the graph s structure i.e., its nodes and edges as this sets it apart from other kinds of visualization. There are different ways to systematize graph layouts and visualization methods. The most prevalent one is to categorize them according to algorithmic considerations [BETT99, HMM00, KW01, Tam13], but there also exist categorizations according to the input data (trees vs. networks, directed vs. undirected, etc.) [BETT94], to the principal visual encoding of the output visualization [vlks 11, SS06], and to the user tasks the visualization supports [APS14]. corresponding author: On top of the structure, additional facets of graphs are frequently included in their visualization. Existing surveys on graph visualization commonly focus on one additional facet to be shown, while other facets are considered as secondary constraints or subtypes: The graph s partitions i.e., any grouping or clustering of the nodes and/or edges are explicitly addressed as part of the research on Compound Graph Visualization, for which a number of common layout techniques exist that handle the specifics of partitioned graphs [BC01,VBW15]. The graph s attributes i.e., its node properties and edge weights play a fundamental role in the field of Multivariate Network Visualization that treats them as a representation challenge in their own right [KPW14]. The graph s dynamics i.e., its time-varying structure is the subject of the field of Dynamic Graph Visualization [BBDW14, KKC14a]. The distinction between static and dynamic graph visualization is considered a primary visualization challenge [Che06]. The graph s spatialization i.e., fixed node positions and sometimes even fixed routes for its edges is usually considered a subdomain of Cartography and most of the literature on (geo)spatial graphs has appeared in this context [Rod05, Wol13]. (a) structure (b) partitions (c) attributes (d) temporal context t (e) spatial context Figure 1: Facets of graph-structured data that are commonly included in graph visualizations. As a result, the mentioned overview articles and surveys provide to a large degree targeted classifications for the particular facet on which they focus. This stands in contrast to many scenarios in which multiple facets of a graph are displayed e.g., visualizations of attributed, spatio-temporal graph structures as they occur for example in wireless mesh networks [HSS11, HSCW13]. These multi-faceted scenarios require a broader view of graph visualization that incorporates the commonly separated facets of graph-structured data. In this report, we aim to reconcile these different perspectives with each other, thereby contributing a high-level overview or meta-survey of the mentioned existing surveys for faceted graph visualization. Our main thesis underlying this report is that each facet of a graph can conceptually be considered as being visualized separately and then being composed into a final multi-faceted visualization. This compositional viewpoint resonates to some degree with most of the existing surveys most prominently in Kerracher et al. s design space for dynamic graph visualization [KKC14a]. In Sec. 2, we distill this idea into a systematization approach that allows us to create a uniform categorization of faceted graph visualizations for a diverse set of facets. Sec. 3 presents such a categorization for combinations of the graph layout with representations of one additional facet out of the four data facets that are commonly encountered with graph data: partitions, attributes, temporal and spatial context. These are schematically depicted in Fig. 1. This categorization effectively reframes the classifications put forward by the existing surveys in a consistent and relatable schema. As Sec. 4 shows, our composition approach also allows us to go beyond the existing surveys of single-faceted graph visualization by combining them into graph visualizations with multiple different facets. Finally to span the full breadth of multi-faceted graph visualization, Sec. 5 discusses visualizations of multiple instances of the same facet, before Sec. 6 concludes this report by highlighting some open research questions. 2. Our Systematization Approach There exist countless instances of visualization techniques for multi-faceted graph data, which makes it impossible to survey these techniques one by one in this report. To solve this problem, we used a systematization approach that is: output-oriented by focusing on the visual result and thus abstracting from other aspects, such as the different ways to produce them (algorithmics) or to use them (user tasks), high-level or generic by abstracting from the concrete visual displays of individual facets and describing their composition instead, and exemplifying visualizations for each composition and discussing them in detail, rather than trying to list them all. These aspects are detailed in the following in order to clarify the methodology we use in this report An Output-oriented View on Graph Visualization In graph visualization, the focus lies traditionally on the algorithms that produce a graph layout with their visual properties being a-priori constrained (e.g., uniform edge lengths) or a- posteriori measured and optimized (e.g., number of edge crossings). This focus stems from the inherent complexity of the graph layout problem, which is intractable in case of contradicting visual constraints and still remains NP-complete when prioritizing them [DPS02] or when reducing the problem to a simpler graph class, such as trees [MS04]. Thus a lot of research is devoted to developing layout heuristics that reduce the problem s algorithmic complexity while maintaining a high visual quality of the outcome. Over the last decade, this focus has slightly shifted towards considerations of the utility of the generated graph layouts for various user tasks. This is only natural, as different tasks impose different requirements on the visualization. For example, an interactive exploratory traversal of a network requires other visual properties than a static overview for its presentation. Hence, recurring tasks for graph visualization have been identified [LPP 06] and subsequently refined for the various graph facets e.g., for partitioned graphs [SSK14], for multivariate graphs [PPS14], and for dynamic graphs [APS14, KKC14b]. In order to handle this variety of the diverse layout algorithms for generating and the numerous ways of using graph visualizations, we recognize that end users are mainly concerned with the final look-and-feel of a visualization We thus adopt an output-oriented perspective that aims to systematize the observable visual encodings, instead of the possibly large number of different ways to produce it or to use it. (a) juxtaposition (b) superimposition (c) nesting Figure 2: Composition mechanisms for two facets in display space exemplified for different graph structures and their geospatial context. Compositions realize different ways of putting focus on a representation: while the juxtaposition (a) provides a balanced view, the superimposition (b) features a clear, underlying base representation that determines the positioning for all overlaid facets. This is also the case for nesting (c), as the nested facet has to obey the positioning and space constraints of the base representation. Depending on the base representation, the possible utilization of the outcome can differ significantly. For example, both instances of nesting (c) show the same data yet, the nested subgraphs on the left convey which nodes belong to a given geospatial area, whereas the nested areas on the right show which areas belong to a given node A High-level Systematization through Composition As the graphical encoding is largely different from facet to facet, each facet would require its own categorization, based on their respective graphics. This is basically the abstraction level used by most of the existing surveys, which focus on a single additional facet e.g., the surveys for dynamic graphs [BBDW14, KKC14a] use such visual distinctions. In order to provide a uniform systematization for all different data facets, we adopt a higher-level approach that focuses on the different ways for combining visualizations of graph facets instead of what these visualizations are. There are a number of possible combinations and we discern them by their base representation and composition modality. The base representation of a combination names the primary graph facet whose depiction governs the central aspects of the composited visualization, whereas any other facet is merely added onto this base representation. For example, when combining the graph structure with its attributes, the base representation can either be a graphical layout of the structure with added visual cues for the attributes; or it can be a multivariate visualization of the attributes that is enhanced with edges to show the structure. The base representation can be more or less pronounced, but can usually be determined if the graph is large enough to prevent equal treatment for each facet due to limited screen space. Whereas for smaller datasets, it may be possible and desirable to show all facets in a balanced way without a discernable focus on one of them. This is either done by placing the representations of both facets in multiple coordinated views [Rob07] and connecting them via linking and brushing [BMMS91], or both facets are considered to be nodes of a bipartite graph [ADH98] and interleaved in a combined visualization. The composition modality denotes whether the combination of the facets is realized through a spatial composition that utilizes the display space, or through a temporal composition that utilizes display time. For both composition modalities exists a variety of realizations. For the spatial composition of visualizations, the literature enumerates different possibilities, such as juxtaposing two visualizations, superimposing them, or nesting them [JE12, GAW 11]. Fig. 2 illustrates these three composition methods for the case of different graph structures being combined with a geospatial facet. For the temporal composition, notable results in the direction of establishing an agreed-upon set of possible realizations have been made [KK95, Fis10]. In principle when combining two facets in display time, we iterate over the elements of one facet and display the corresponding other facet. For example, in dynamic graph visualization, we could either iterate over the temporal facet and show the graph structure present at each time point to analyze the dynamic network, or we could traverse the structural facet and highlight all time points at which a node is present to investigate the network dynamics. We discern between two degrees of freedom for steering such an iteration: predefined compositions run automatically, as in an animation, and freely adjustable compositions allow the user to determine the sequence of views on the fly via appropriate GUI controls. In general, spatial and temporal composition are challenging and despite much research on them, there remain a number of hard algorithmic questions to which no final answers have been found yet. A common problem of the spatial composition is edge clutter of a superimposed or nested graph structure that obscures the underlying base representation. The most prominent solution to this problem is the use of edge bundling [ZXYQ13]. Whereas the most challenging problem of the temporal composition is to create a base representation that remains coherent over the course of the iteration and preserves the mental map [Bra01]. This is usually achieved by confining layout changes to only those local rec The Eurographics Association 2015. gions in which underlying data changes occur, while keeping the global layout stable [BIM12, MELS95]. In case of both composition modalities being used for different facets, it can also occur that both challenges must be addressed concurrently for example in the form of an edge bundling that is stabilized over the course of an animation [HEF 14] Exemplification instead of Enumeration While other surveys aim to provide a complete enumeration of existing visualizations (e.g., [Sch11]), this is impossible for multi-faceted graph visualization techniques, as there are simply too many. This is underlined by the fact that each of the considered facets forms the subject of its own domain in visualization: Displaying partitions and clusters is addressed in Euler diagrams [Rod13] and set visualization [AMA 14]. Showing (numerical) attributes of data is the concern of multivariate visualization [WB97, FH09]. Representing dynamic data is the challenge of visualization for time-oriented data [AMST11, Wil12]. Depicting spatial data is mainly understood as showing geospatial data and addressed in cartography [KO10] and geographic visualization [DMK05, DMT08]. The combinations of the many individual techniques these domains comprise into multi-faceted visualizations is sheer endless and modern multi-view visualization systems can easily be configured to produce hundreds of different combinations. Therefore, we concentrate on only a few examples per combination possibility and facet, which allows us in turn to provide a more detailed description of them. They stand as representatives for other, often similar visualization techniques that fall into the same category. 3. Visualizations of the Graph Structure and One Additional Facet In this section, we present the proposed categorization by systematically discussing all possible combinations of a visualization of the graph structure (G) with a visualization of one additional facet ( ). Together with the composition mechanisms introduced in the previous section, this generates the following five combinations: Spatial composition of two facets means that they must both be accommodated in the same visualization, with the base representation determining the principal visual encoding. We denote this composition by straight arrows a one-sided arrow pointing towards the base representation in which the other one is incorporated, and a double-sided arrow when both representations are combined in a balanced way without a particular focus on one of them. [G ] Using the graph structure in the base representation implies that an underlying graph layout is enhanced via superimposition or nesting with a visual representation of the respective other facet. [G ] A balanced display of two facets can be achieved by juxtaposing them either with each facet in its own display space as linked views or by interleaving them in the same display space as a bipartite graph. [ G] Using the other facet in the base representation implies that this facet is visualized and the graph structure is added onto it by means of superimposition or nesting. Temporal composition of two facets means that we only show the base representation and iterate over the other facet. As the facet over which the iteration runs remains mostly invisible, there cannot be a balanced composition in display time, because the visible base representation clearly determines the visual appearance. Another difference to the spatial composition is that the visualization is not produced once, but reproduced for each iteration step. This aspect of an iteratively changing display is embodied in the circular arrow that we use to denote this composition. [G ] Using the graph structure in the base representation implies that the user iterates over the respective other facet and sees the corresponding parts of the structure e.g., looping through a list of spatial regions and showing the subgraph(s) that belong to each region. [ G] Using the other facet in the base representation implies that the user traverses the graph structure by iterating over the nodes and/or edges and thus adapts the display of the other facet to show only those items that relate to it e.g., stepping through the nodeset of the graph to see which spatial regions they lie in. In the following, these five types of composition are applied to the four facets of partitions ( = P), attributes ( = A), time ( = T ), and space ( = S). The resulting categorization for each facet is compared to the classifications derived by other surveys for the individual single-faceted graph visualizations Partitions: Compound Graph Visualization Combining the graph structure and its partitioning in one visual display is often done to show graphs that would be too large to be shown in an unclustered, fully detailed way. Such a partitioning can either be a classification that is given with the graph-structured dataset or a computed clustering for which a wide range of methods exists [Sch07]. Often, partitions are given and shown in form of a hierarchy (e.g., a dendrogram) with larger partitions including smaller ones Spatial Compositions [G P] Graph structure as base representation: The first figure in Table 1 shows the level-of-detail visualization technique [BD07] that takes a given 3D layout of the graph structure and constructs semi-transparent implicit surfaces around groups of nodes of the same partition. Note that in order to yield discernable clusters, the underlying layout must separate them well [NL05]. The nodes are classes of an objectoriented software and the edges denote method calls among S. Hadlak, H. Schumann, H.-J. Schulz / A Survey of Multi-faceted Graph Visualization Table 1: Examples for combinations of structure and partitions in one visualization. balanced representation partitions as base representation spatial composition structure as base representation [G P] Level-of-Detail Visualization [BD07] [G P] Coordinated Graph Visualization [TA
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