Detecting and visualizing what are the most relevant changes in an evolving network is an open challenge in several domains. We present a fast algorithm that filters subsets of the strongest nodes and edges representing an evolving weighted graph and visualize it by either creating a movie, or by streaming it to an interactive network visualization tool. The algorithm is an approximation of exponential sliding time-window that scales linearly with the number of interactions. We compare the algorithm against rectangular and exponential sliding time-window methods. Our network filtering algorithm: (i) captures persistent trends in the structure of dynamic weighted networks, (ii) smoothens transitions between the snapshots of dynamic network, and (iii) uses limited memory and processor time. The algorithm is publicly available as open-source software.
More in general, there are several open fronts in empirical research in graph visualization to identify the impact of certain factors on the quality of the animation (e.g., speed @cite_69 , interactivity @cite_36 ). An extensive overview of this aspect has been conducted recently by @cite_15 . Methods to preserve the stability of nodes and the consistency of the network structure leveraging hierarchical organization on nodes have been proposed @cite_5 @cite_14 @cite_68 @cite_47 . User studies have shown that hierarchical approaches that collapse several nodes in larger meta-nodes can improve graph readability in cases of high edge density @cite_24 . The graph layout also has a significant impact on the readability of graphs @cite_8 . Some work has been done to adapt spectral and force-directed graph layouts @cite_61 to that recompute the position of nodes at time @math based on the previous positions at time @math - @math minimizing displacement of vertices @cite_66 @cite_63 @cite_54 @cite_72 or to propose new stress-minimization'' strategies to map the changes in the graph @cite_60 .
@cite_61 @cite_69 @cite_14 @cite_47 @cite_8 @cite_36 @cite_60 @cite_54 @cite_24 @cite_72 @cite_63 @cite_5 @cite_15 @cite_68 @cite_66
1520174226 2099718964 1502972208 1489443448 1584092895 2167252678 2047854635 2513172345 2141026840 2100112610 1524145331 1533210402 1969957132 2111781385 2111244106
Graph layout methods described in previous chapters were based on structural characteristics of the graph, or a preprocessed version of the graph. Often, such knowledge is not provided. In this chapter, we take a look at a class of methods applicable to general graphs, without prior knowledge of any structural properties. Their common denominator is that they liken the graph to a system of interacting physical objects, the underlying assumption being that relaxed (energy-minimal) states of suitably defined systems correspond to readable and informative layouts. Effective visualization of dynamic graphs remains an open research topic, and many state-of-the-art tools use animated node-link diagrams for this purpose. Despite its intuitiveness, the effectiveness of animation in node-link diagrams has been questioned, and several empirical studies have shown that animation is not necessarily superior to static visualizations. However, the exact mechanics of perceiving animated node-link diagrams are still unclear. In this paper, we study the impact of different dynamic graph metrics on user perception of the animation. After deriving candidate visual graph metrics, we perform an exploratory user study where participants are asked to reconstruct the event sequence in animated node-link diagrams. Based on these findings, we conduct a second user study where we investigate the most important visual metrics in depth. Our findings show that node speed and target separation are prominent visual metrics to predict the performance of event sequencing tasks. © 2012 Wiley Periodicals, Inc. We propose a heuristic for dynamic hierarchical graph drawing. Applications include incremental graph browsing and editing, display of dynamic data structures and networks, and browsing large graphs. The heuristic is an on-line interpretation of the static layout algorithm of Sugiyama, Togawa and Toda. It incorporates topological and geometric information with the objective of making layout animations that are incrementally stable and readable through long editing sequences. We measured the performance of a prototype implementation. This paper presents a technique for visualizing the differences between two graphs. The technique assumes that a unique labeling of the nodes for each graph is available, where if a pair of labels match, they correspond to the same node in both graphs. Such labeling often exists in many application areas: IP addresses in computer networks, namespaces, class names, and function names in software engineering, to name a few. As many areas of the graph may be the same in both graphs, we visualize large areas of difference through a graph hierarchy. We introduce a path-preserving coarsening technique for degree one nodes of the same classification. We also introduce a path-preserving coarsening technique based on betweenness centrality that is able to illustrate major differences between two graphs. Social network analysis uses techniques from graph theory to analyze the structure of relationships among social actors such as individuals or groups. We investigate the effect of the layout of a social network on the inferences drawn by observers about the number of social groupings evident and the centrality of various actors in the network. We conducted an experiment in which eighty subjects provided answers about three drawings. The subjects were not told that the drawings were chosen from five different layouts of the same graph. We found that the layout has a significant effect on their inferences and present some initial results about the way certain Euclidean features will affect perceptions of structural features of the network. There is no “best” layout for a social network; when layouts are designed one must take into account the most important features of the network to be presented as well as the network itself. Several previous systems allow users to interactively explore a large input graph through cuts of a superimposed hierarchy. This hierarchy is often created using clustering algorithms or topological features present in the graph. However, many graphs have domain-specific attributes associated with the nodes and edges, which could be used to create many possible hierarchies providing unique views of the input graph. GrouseFlocks is a system for the exploration of this graph hierarchy space. By allowing users to see several different possible hierarchies on the same graph, the system helps users investigate graph hierarchy space instead of a single fixed hierarchy. GrouseFlocks provides a simple set of operations so that users can create and modify their graph hierarchies based on selections. These selections can be made manually or based on patterns in the attribute data provided with the graph. It provides feedback to the user within seconds, allowing interactive exploration of this space. Abstract As a consequence of the rising interest in longitudinal social networks and their analysis, there is also an increasing demand for tools to visualize them. We argue that similar adaptations of state-of-the-art graph-drawing methods can be used to visualize both, longitudinal networks and predictions of stochastic actor-oriented models (SAOMs), the most prominent approach for analyzing such networks. The proposed methods are illustrated on a longitudinal network of acquaintanceship among university freshmen. Spectral methods are naturally suited for dynamic graph layout, because moderate changes of a graph yield moderate changes of the layout under weak assumptions. We discuss some general principles for dynamic graph layout and derive a dynamic spectral layout approach for the animation of small-world models. Graph visualization systems often exploit opaque metanodes to reduce visual clutter and improve the readability of large graphs. This filtering can be done in a path-preserving way based on attribute values associated with the nodes of the graph. Despite extensive use of these representations, as far as we know, no formal experimentation exists to evaluate if they improve the readability of graphs. In this paper, we present the results of a user study that formally evaluates how such representations affect the readability of graphs. We also explore the effect of graph size and connectivity in terms of this primary research question. Overall, for our tasks, we did not find a significant difference when this clustering is used. However, if the graph is highly connected, these clusterings can improve performance. Also, if the graph is large enough and can be simplified into a few metanodes, benefits in performance on global tasks are realized. Under these same conditions, however, performance of local attribute tasks may be reduced. This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and, thus, the user's mental map while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided. In this paper we present a generic algorithm for drawing sequences of graphs. This algorithm works for different layout algorithms and related metrics and adjustment strategies. It differs from previous work on dynamic graph drawing in that it considers all graphs in the sequence (offline) instead of just the previous ones (online) when computing the layout for each graph of the sequence. We introduce several general adjustment strategies and give examples of these strategies in the context of force-directed graph layout. Finally some results from our first prototype implementation are discussed. Graph drawings are a basic component of user interfaces that display relationships between objects. Generating incrementally stable layouts is important for many applications. This paper describes DynaDAG, a new heuristic for incremental layout of directed acyclic graphs drawn as hierarchies, and its application in the DynaGraph system. The usage of visualizations to aid the analysis of time oriented data plays an important role in various fields of applications. The need to visualize such data was decisive for the development of different visualization techniques over the last years. One of the frequently applied techniques is animation in order to illustrate the movements in such a way to make changes in the data transparent. However, evaluation studies of such animated interfaces for time-oriented data with potential users are still difficult to find. In this paper, we present our observations based on a systematic literature review with the motivation to support researchers and designers to identify future directions for their research. The literature review is split in two parts: (1) research on animation from the field of psychology, and (2) evaluation studies with the focus on animation of time-oriented data. We describe TopoLayout, a feature-based, multilevel algorithm that draws undirected graphs based on the topological features they contain. Topological features are detected recursively inside the graph, and their subgraphs are collapsed into single nodes, forming a graph hierarchy. Each feature is drawn with an algorithm tuned for its topology. As would be expected from a feature-based approach, the runtime and visual quality of TopoLayout depends on the number and types of topological features present in the graph. We show experimental results comparing speed and visual quality for TopoLayout against four other multilevel algorithms on a variety of data sets with a range of connectivities and sizes. TopoLayout frequently improves the results in terms of speed and visual quality on these data sets Many graph drawing (GD) scenarios are dynamic inasmuch as they involve a repeated redrawing of the graph after frequently occurring changes to the graph structure and or some layout properties.