CPSC 533C Project Proposal

Stephen Ingram
sfingramATcsDOTubcDOTca

Overview | Solution | Scenario | Implementation | Milestones | Update

Overview

Proposed InfoVis Solution

My proposed solution is an implementation of Frank van Ham and Jarke J. van Wijk's "Interactive Visualization of Small World Graphs." This involves laying out the graph with a r-PolyLog physics simulator. The nodes are then clustered using a proximity-based dendrogram clustering. Nodes are rendered as spheres according to the number of subclusters/nodes they contain, and edges. The user interacts with the graph using the mouse as a focal tool. This tool controls the Degree of Abstraction (DOA) of a given region of the screen (DOA quantifying the granularity of the clustering). The DOA is a function of distance to the center of the focal tool. At the highest granularity, the focal tool acts as a geometric fisheye distortion.

Scenario

The user would start by choosing algorithm specific settings or just going with the defaults. They would proceed by loading a graph dataset. The user then waits while the software performs its pre-processing steps, physical layout and proximity clustering with dendrograms. They observe the initial layout as large nodes with thick edges, these are the major clusters of the graph. This will have a meaning specific to the semantics of the graph but usually it's where a large set of nodes share features or communication. To gain knowledge about the subclusters in the graph, the user moves the mouse focus (clearly indicated with a focal circle) into the graph towards one of these large nodes. This causes it to break into smaller and smaller nodes proportional to the distance of the focus, edges appear, and the user can observer the finer grained clusters of the graph. As the clusters become less and less abstract, the user observes the makeup of the graph, ie which clusters more strongly communicate or relate to which clusters. This process continues, the user passing the mouse over various parts of the graph, until they form a satisfying mental model of the graph's hierarchical structure.
The initial layout of the graph.
The graph with the DOA/fisheye focus placed over clusters. Note how the larger clusters have separated into smaller clusters, introducing new nodes and edges.

These images are taken directly from the paper Interactive Visualization of Small World Graphs by Frank van Ham and Jarke J. van Wijk, Proceedings of the IEEE Symposium on Information Visualization.

Implementation:

I propose to implement this tool as a series of prefuse components in Java using Eclipse. The resulting implementation will run as an applet or with JavaWebStart. An added benefit of developing prefuse components is that they will be readily available for other info-vis software projects that use the prefuse toolkit.

Milestones:

  1. Write New Node Renderer code for Spherical Nodes and clusters
    • modify/rewrite existing node-rendering code for nodes and aggregates
    • FAILSAFE: Just draw nodes as circles
    • ESTIMATED IMPLEMENTATION TIME: 1/2 WEEK
  2. Implementation of "constant volume" Edge renderer
    • rewrite existing edge renderer
    • FAILSAFE: Just draw edges as lines
    • ESTIMATED IMPLEMENTATION TIME: 1/2 WEEK
  3. Implementation of Fisheye DOA Layout
    • Rewrite existing layout code to handle expansion of aggregations based on distance to focal point
    • Rewrite existing fisheye layout code to distort geometric positions of nodes based on distance to focal point
    • FAILSAFE: Use existing fisheye filter
    • ESTIMATED IMPLEMENTATION TIME: 2 WEEKS
  4. Implementation of run-once dendrogram clustering generation
    • Write algorithm as prefuse filter
    • Write prefuse aggregation objects
    • WISHLIST: Spatial Subdivision Optimization
    • FAILSAFE: Use a pre-clustered dataset
    • ESTIMATED IMPLEMENTATION TIME: 1 WEEK
  5. Implementation of run-once r-PolyLog physics simulation layout
    • Modify/Rewrite existing layout code
    • WISHLIST: Perform Barnes-Hut optimization
    • FAILSAFE: Use the existing prefuse physics engine
    • ESTIMATED IMPLEMENTATION TIME: 2 WEEKS

Update Powerpoint (11/16/05)