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
|
