The project Analysis and Visualization of Complex Graphs is supported by the NSF under grant #IIS-0534485, and by NVIDIA Corp.

Objectives:

1. Multi-scale analysis based on a coarsening approach that preserves metric structure similar to how multidimensional scaling and isomap preserve metric structure during dimensionality-reducing projections.
2. Focusing on power-law "scale-free" networks that arise, like fractals, in natural and man-made settings.
3. Using advanced GPU and hair-rendering techniques to visualize graphics with more edges than pixels.

Personnel

• Adj. Prof. Michael Garland, now an NVIDIA researcher, proposed the original project and remains an active contributor to the project.
• Prof. John C. Hart leads the project.
• Yuntao Jia is a Ph.D. student and project RA working on complex graph analysis, simplification and visualization.
• Apeksha Godiyal is an M.S. student and project RA working on efficient layout of large graphs.
• Jared Hoberock, Ph.D. 2008 now an NVIDIA researcher, worked on GPU and shader-based display of complex graphs.

Timeline

• Year 1:
  • Design and implement basic coarsening and multi-level graph framework.
  • Develop method for reliably stratifying scale-free networks.
  • Explore basic fiber rendering model.
  • Explore algebraic coarsening methods.
• Year 2:
  • Begin implementation of high-performance interactive rendering system designed to achieve peak performance on modern graphics systems.
  • Extend fiber rendering modelwith self-shadowing.
  • Test the effectiveness of visual cues in understanding structure.
  • Implement shortest path, centrality, etc. computations on top of multi-level structure.
• Year 3:
  • Finalize high-performance rendering system.
  • Extensive empirical analysis of both coarsening and rendering systems.
  • Finalize and distribute software system.
  • Begin designing extensions to handle truly massive graphs larger than main memory.

Current Results

We have proposed a graph simplification method for visualizing power-law graphs. Our method simplifies the graph by filtering its edges based on their importance. Comparing with previous methods, our method improves the visualization of power-law graph dramatically. A comparison on the protein interaction graph is shown in the following figure

The work flow of our algorithm is explained as follows

The following figure shows our result on a graph which represents 6,625,280 friendships of 820,878 users on the photo sharing website flickr.com. For such massive graphs containing more edges than pixels, we have also applied rendering techniques to better indicate the hubs in the simplified graph, including anisotropic shading (middle) and edge coloring (right).