Source Code Available
The Walrus source code is available on GitHub under the GNU GPL.
Description
Walrus is a tool for interactively visualizing large directed graphs in three-dimensional space. It is technically possible to display graphs containing a million nodes or more, but visual clutter, occlusion, and other factors can diminish the effectiveness of Walrus as the number of nodes, or the degree of their connectivity, increases. Thus, in practice, Walrus is best suited to visualizing moderately sized graphs that are nearly trees. A graph with a few hundred thousand nodes and only a slightly greater number of links is likely to be comfortable to work with.
Walrus computes its layout based on a user-supplied spanning tree. Because the specifics of the supplied spanning tree greatly affect the resulting display, it is crucial that the user supply a spanning tree that is both meaningful for the underlying data and appropriate for the desired insight. The prominence and orderliness that Walrus gives to the links in the spanning tree, in contrast to all other links, means that an arbitrarily chosen spanning tree may create a misleading or ineffective visualization. Ideally, the input graphs should be inherently hierarchical.
Walrus uses 3D hyperbolic geometry to display graphs under a fisheye-like distortion. At any moment, the amount of magnification, and thus the level of visible detail, varies across the display. This allows the user to examine the fine details of a small area while always having a view of the whole graph available as a frame of reference. Graphs are rendered inside a sphere that contains the Euclidean projection of 3D hyperbolic space. Points within the sphere are magnified according to their radial distance from the center. Objects near the center are magnified, while those near the boundary are shrunk. The amount of magnification decreases continuously and at an accelerated rate from the center to the boundary, until objects are reduced to zero size at the latter, which represents infinity. By bringing different parts of a graph to the magnified central region, the user can examine every part of the graph in detail.
Applicability
Please note that Walrus currently has the following requirements, restrictions, or limitations which may render it unsuitable for a given problem domain or dataset:
- Only directed graphs are supported.
- Only connected graphs with reachable nodes are supported. All nodes must be reachable from all other nodes if the direction of links is disregarded, and all nodes must be reachable from the root node if the direction of links is enforced.
- A meaningful spanning tree is required. The spanning tree must be meaningful with respect to the problem domain, dataset, research hypothesis, or in some other way. It must not be arbitrary. (This is a crucial requirement. Difficulty in coming up with such a spanning tree is a sure sign that Walrus is unsuitable for the task.) Note that this requirement does not preclude cycles or other non-tree links in the graph itself.
- Multiple links are not supported. There cannot be more than one link connecting together any given pair of nodes. In particular, undirected graphs cannot be simulated with bidirectional links.
- Dynamically changing graphs are not supported. It is not possible to alter the structure or content of a graph once loaded or to update the display based on a data feed.
- Only one graph may be loaded at any time. In particular, two graphs cannot be loaded for side-by-side comparison.
- Slight changes in the structure of a graph may lead to dramatically different graph layouts. It may be difficult to compare related graphs, such as those representing snapshots of an evolving dataset.
- Only LibSea graph files (a documented CAIDA-developed input format) are supported.
- Walrus is a standalone application and not an API. It cannot be incorporated into other applications.
- Walrus cannot be used as an applet.
Galleries
The following galleries show graphs of various sizes and complexity. Some are network topology graphs derived from skitter measurements, with sizes ranging from ten thousand to five hundred thousand nodes. Others represent our web site directory hierarchy (around fourteen thousand nodes), CVS repository (around eighteen thousand nodes), and directory trees.
Visualization and Navigation | Abstract Art |
Implemented Features
- rendering at a guaranteed framerate regardless of graph size
- coloring nodes and links with a fixed color, or by RGB values stored in attributes
- labelling nodes
- picking nodes to examine attribute values
- displaying a subset of nodes or links based on a user-supplied boolean attribute
- interactive pruning of the graph to temporarily reduce clutter and occlusion
- zooming in and out
Requirements
Walrus requires Java3D v1.2.1 (or later) and JDK 1.3.0 (or later). A hardware-accelerated graphics card with OpenGL support is required (on Windows systems, you must use the OpenGL version of Java3D and not the DirectX version). It is also necessary to have a speedy machine with lots of memory (128MB is probably a minimum; 256MB or more is better; 512MB is probably required for a few hundred thousand nodes).
Walrus was developed and tested on a Sun Ultra 60 with an Elite 3D card and 512MB of RAM, running Solaris 7, a box graciously donated by Sun.
References
Tamara Munzner worked out many of the ideas and techniques underlying Walrus in her Ph.D thesis. Her other publications are also good resources.
Another related work is the hyperbolic tree viewer at Inxight. Walrus differs from their product in at least three ways. We work in 3D instead of 2D, use the Klein model of hyperbolic geometry instead of the Poincare, and use a very different layout algorithm. Laying out graphs in 3D is challenging, as occlusion along the line of sight diminishes some of the benefits of the additional dimension. Hence, 3D layout algorithms can differ considerably from similar 2D algorithms. Walrus uses a modified version of the H3 layout algorithm designed by Munzner.
Resources on hyperbolic geometry:
- NonEuclid. An introduction to hyperbolic geometry. It includes an interactive Java applet for creating straightedge and compass constructions in the Poincare model.
- The Hyperbolic Geometry Exhibit. An introduction to hyperbolic geometry at the Geometry Center.
- David C. Royster. Neutral and Non-Euclidean Geometries. Lecture notes that explore the mathematical details of hyperbolic geometry.
- Mark Phillips and Charlie Gunn. Visualizing hyperbolic space: Unusual uses of 4x4 matrices. In 1992 Symposium on Interactive 3D Graphics (Boston, MA, March 29 - April 1, 1992). A paper giving the 4x4 matrices for performing reflections, translations, and rotations in the Klein model. It also gives a formulation of the hyperbolic distance function, which computes the hyperbolic distance between any two Euclidean points in the model.
Resources on graph drawing:
- Graph Drawing. A starting point for graph drawing. It includes a bibliography and links to research groups, tools, conferences, and selected papers.
- Graph Visualization and Navigation in Information Visualization. A survey paper on techniques for visualizing graphs, especially from the perspective of information visualization.
- Fractal Approaches for Visualizing Huge Hierarchies. A paper discussing a fractal-based tree layout algorithm.
Resources on nonlinear magnification:
- Nonlinear Magnification Home Page. A starting point for nonlinear magnification. It includes a survey of techniques and a large collection of links to relavant papers.
- Manojit Sarkar and Marc H. Brown. Graphical Fisheye Views of Graphs. A distortion-based approach in 2D that uses a nonlinear magnification function rather than hyperbolic geometry.
Acknowledgments
Support for this work was provided by the NSF CAIDA and Internet Atlas grants (ANI-9711092 and ANI-9996248), the DARPA NGI and NMS programs (N66001-98-2-8922 and N66001-01-1-8909), Sun Microsystems, and CAIDA members.