An official website of the United States government
Large tree structures are ubiquitous and real-world relational datasets often have information associated with nodes (e.g., labels or other attributes) and edges (e.g., weights or distances) that need to be communicated to the viewers. Yet, scalable, easy to read tree layouts are difficult to achieve. We consider tree layouts to be readable if they meet some basic requirements: node labels should not overlap, edges should not cross, edge lengths should be preserved, and the output should be compact. There are many algorithms for drawing trees, although very few take node labels or edge lengths into account, and none optimizes all requirements above. With this in mind, we propose a new scalable method for readable tree layouts. The algorithm guarantees that the layout has no edge crossings and no label overlaps, and optimizing one of the remaining aspects: desired edge lengths and compactness. We evaluate the performance of the new algorithm by comparison with related earlier approaches using several real-world datasets, ranging from a few thousand nodes to hundreds of thousands of nodes. Tree layout algorithms can be used to visualize large general graphs, by extracting a hierarchy of progressively larger trees. We illustrate this functionality by presenting several map-like visualizations generated by the new tree layout algorithm.
more »
« less
Multi-level tree based approach for interactive graph visualization with semantic zoom
A recent data visualization literacy study shows that most people cannot read networks that use hierarchical cluster representations such as “supernoding” and “edge bundling.” Other studies that compare standard node-link representations with map-like visualizations show that map-like visualizations are superior in terms of task performance, memorization and engagement. With this in mind, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for maplike visualization of large graphs that is representative, real, persistent, overlapfree labeled, planar, and compact. These six desirable properties are formalized with the following guarantees: (1) The abstract and embedded trees represent the underlying graph appropriately at different level of details (in terms of the structure of the graph as well as the embedding thereof); (2) At every level of detail we show real vertices and real paths from the underlying graph; (3) If any node or edge appears in a given level, then they also appear in all deeper levels; (4) All nodes at the current level and higher levels are labeled and there are no label overlaps; (5) There are no crossings on any level; (6) The drawing area is proportional to the total area of the labels. This algorithm is implemented and we have a functional prototype for the interactive interface in a web browser.
more »
« less
- PAR ID:
- 10109414
- Date Published:
- Journal Name:
- ArXiv.org
- ISSN:
- 2331-8422
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Some of the basic properties of any dynamical system can be summarized by a graph. The dynamical systems in our theory run from maps like the logistic map to ordinary differential equations to dissipative partial differential equations. Our goal has been to define a meaningful concept of graph of any dynamical system. As a result, we base our definition of “chain graph” on “epsilon-chains”, defining both nodes and edges of the graph in terms of chains. In particular, nodes are often maximal limit sets and there is an edge between two nodes if there is a trajectory whose forward limit set is in one node and its backward limit set is in the other. Our initial goal was to prove that every “chain graph” of a dynamical system is, in some sense, connected, and we prove connectedness under mild hypotheses.more » « less
-
Edge bundling is a promising graph visualization approach to simplifying the visual result of a graph drawing. Plenty of edge bundling methods have been developed to generate diverse graph layouts. However, it is difficult to defend an edge bundling method with its resulting layout against other edge bundling methods as a clear theoretic evaluation framework is absent in the literature. In this paper, we propose an information-theoretic framework to evaluate the visual results of edge bundling techniques. We first illustrate the advantage of edge bundling visualizations for large graphs, and pinpoint the ambiguity resulting from drawing results. Second, we define and quantify the amount of information delivered by edge bundling visualization from the underlying network using information theory. Third, we propose a new algorithm to evaluate the resulting layouts of edge bundling using the amount of the mutual information between a raw network dataset and its edge bundling visualization. Comparison examples based on the proposed framework between different edge bundling techniques are presented.more » « less
-
Edges in many real-world social/information networks are associated with rich text information (e.g., user-user communications or user-product reviews). However, mainstream network representation learning models focus on propagating and aggregating node attributes, lacking specific designs to utilize text semantics on edges. While there exist edge-aware graph neural networks, they directly initialize edge attributes as a feature vector, which cannot fully capture the contextualized text semantics of edges. In this paper, we propose Edgeformers, a framework built upon graph-enhanced Transformers, to perform edge and node representation learning by modeling texts on edges in a contextualized way. Specifically, in edge representation learning, we inject network information into each Transformer layer when encoding edge texts; in node representation learning, we aggregate edge representations through an attention mechanism within each node’s ego-graph. On five public datasets from three different domains, Edgeformers consistently outperform state-of-the-art baselines in edge classification and link prediction, demonstrating the efficacy in learning edge and node representations, respectively.more » « less
-
Graphs are most often visualized in the two dimensional Euclidean plane, but spherical space offers several advantages when visualizing graphs. First, some graphs such as skeletons of three dimensional polytopes (tetrahedron, cube, icosahedron) have spherical realizations that capture their 3D structure, which cannot be visualized as well in the Euclidean plane. Second, the sphere makes possible a natural “focus + context" visualization with more detail in the center of the view and less details away from the center. Finally, whereas layouts in the Euclidean plane implicitly define notions of “central" and “peripheral" nodes, this issue is reduced on the sphere, where the layout can be centered at any node of interest. We first consider a projection-reprojection method that relies on transformations often seen in cartography and describe the implementation of this method in the GMap visualization system. This approach allows many different types of 2D graph visualizations, such as node-link diagrams, LineSets, BubbleSets and MapSets, to be converted into spherical web browser visualizations. Next we consider an approach based on spherical multidimensional scaling, which performs graph layout directly on the sphere. This approach supports node-link diagrams and GMap-style visualizations, rendered in the web browser using WebGL.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
