Scalable Visualization and Constrained Interaction for Large Graphs
Brynjar Gretarsson, Peterson Trethewey, Svetlin Bostandjiev, and Tobias Höllerer
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.
Presentations and PublicationsScalable visualization and constrained interaction for large graphs.
ITIC Knowledge Discovery and Dissemination (KDD) Conference, McLean, VA, USA, October 3-4 2006.
AcknowledgmentsThis 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.