Stephen Ingram sfingramATcsDOTubcDOTca
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.
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.
Scenario
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. |
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:
Update Powerpoint (11/16/05)