Subdivision Graphs:

Scalable Visualization and Constrained Interaction for Large Graphs


Brynjar Gretarsson, Peterson Trethewey, Svetlin Bostandjiev, and Tobias Höllerer

Overview

We present visualization and interaction techniques for enabling dynamic force-based visualizations of large graphs consisting of tens of thousands of nodes. In rough analogy to the computer graphics concept of subdivision surfaces, we introduce Subdivision Graphs, representing directed or undirected graphs at multiple levels of detail. We evaluated several connectivity-based clustering techniques to automatically create a hierarchy of increasingly complex representations of our target graph, allowing for interaction and introduction of layout constraints at each level. By performing the force-based graph layout incrementally, starting with the highest level of abstraction, we limit the force calculations to small clusters of nodes, keeping the visualization and interaction at real-time speeds even for very large graph structures. Storing the overall layout parameters of the graph backbones at different levels of detail, we are able to maintain a predictable visual model, a so-called "personalized normal form" layout. We apply our techniques to the visualization of large-scale social networks.

The main contributions of this project lie in the design, implementation, and evaluation of novel methodology to better represent, understand, navigate, manipulate, annotate, and share the large graph structures resulting from previous data-fusion, -querying, and -mining steps. Instead of solely providing a visualization backend, the focus is on scalable interaction with potentially dynamically changing data that comes streaming in from various sources. Our graph layout algorithm needs to be deterministic so that laying out the same graph multiple times will result in the same layout.

Details

General Approach

Initially we implemented a spring model that lays out the graph in either 3D or 2D. The layout is computed using three main forces. We treat the edges of the graph as springs, so pulling one node will also move any connected node according to the spring formula. This ensures that connected nodes are placed close together. The second force is a repelling force, which works so that unconnected nodes repel each other to ensure that unconnected nodes do not get too close together or even overlap. The third force pulls the nodes towards the center of gravity to ensure that unconnected components do not fly too far away from the rest of the graph.

Level of Detail Approach

Our solution uses a clustering algorithm to find clusters within the given graph and those clusters are used to simplify the layout algorithm. We automatically cluster the graph and collapse areas of the graph into cluster nodes at many different levels of detail. We can then present the user with a simpler graph which is easier to understand and then the user can take a closer look at the parts of the graph that she is interested in. This also helps us lay out the graph faster, because we can first lay out the simpler graph and then subsequently lay out the subgraphs. This enables us to dynamically lay out the graph as the user interacts with it, even for more than ten thousand nodes. Additionally, the user can save a personalized normal form of the graph to preserve familiarity. Using our subdivision graphs method we can make it easier for users to understand the overall structure of the graph, since they can see the big picture by looking at the graph at cluster level and then they can look into parts of interest in more detail. Users have the option of selecting a single cluster node and opening it to see the contained nodes, or they can click on one button to open up all the cluster nodes and see the whole graph.

Architecture

Our system was incorporated into Blackbook, which we had the source code for because of our cooperation with the intelligence community. Here to the right is a figure of the system architecture. DNV (or Dynamic Network Viewer) is our new visualizer for Blackbook and is instantiated by the class RYO, which is the main class of Blackbook. Our system consists of two main components, GraphDisplayer, which takes care of displaying the graph, and SpringModel, which takes care of laying out the graph according to our layout algorithm. These two classes run as seperate threads (defined by the Timer classes).

Presentations and Publications

Scalable visualization and constrained interaction for large graphs.
ITIC Knowledge Discovery and Dissemination (KDD) Conference, McLean, VA, USA, October 3-4 2006.
PPT

Related Projects

PeerChooser: Visual Interactive Recommendation

Acknowledgments

This research was sponsored in part by ITIC/KDD project "Scalable Visualization and Constrained Interaction for Large Graphs - Supporting the Collaborative Analysis of High-dimensional Data Sets" under NSF grant #0635492.