Deco
max planck institut
informatik
mpii logoMinerva of the Max Planck Society
 

Exploratory Data Analysis and Interactive Visualizations – Winter Semester 2009/2010

Mike Sips (VIS)     Arturas Mazeika (Data Mining)

Extending Walrus for Graph Diffs

<(sensor networks in web contexts)p>Walrus is a large directed graphs visualization tool in three-dimensional space (cf. Figure 1). It is proved to be able to display graphs containing hundreds of thousands of nodes and edges and is by far the most scalable graph visualization tool. Walrus is able to visualize very large graphs because of two reasons: the tool uses (i) a spanning tree as a backbone of the visualization and (ii) a three-dimensional hyperbolic geometry. The spanning tree simplifies the layouting of the graph in 3D space: The graph is first visualized as a tree and then other edges between the nodes are drawn. The three-dimensional hyperbolic geometry serves two purposes. First, it provides an exponential increase of volume as the radius increases (in contrast to third-degree polynomial increase in the Euclidean space). This allows more information visualization. Second, the hyperbolic visualization results in a fish-eye distortion, allowing the user to focus on both the detail of selected scene and overall structure of the graph.
Figure 1: Walrus graph visualization tool
site 1
(a) www.dfid.gov.uk		 site 2
(b) www.pm.gov.uk		 site 3
(c) www.raf.mod.uk

We suggest two projects to extend and analyze graph visualizations with walrus: (i) analysis of web graphs with walrus type of visualizations and (ii) extension of walrus for evolving graphs.

Project 1: Analysis of web graphs with walrus Project 2: Extension of walrus for evolving graphs
The essence of the project is to understand what kind of patters, trends, and properties of graphs are possible to analyze with walrus, and what patterns, trends, and properties are not possible to analyze with the tool. Suggested milestones and objectives:
  1. Install and play with the walrus package
  2. Visualize available web archive data
  3. Understand the technology behind the walrus: hyperbolic coordinates
  4. Search for graph generators; understand their main properties
  5. Play with graphs of sites; understand the properties of the graphs of sites
  6. Write your own graph generator. Vary graphs how much they are tree like, number of densely connected subclusters/subgraphs, etc.
  7. Understand which properties of graphs you can see from the visualization
  8. Understand the sensitivity of the visualization to change of the underlying tree structure
The essence of the project is to change patterns of web graphs. (One of the) Two scenarios can be considered in the project: visualization and analysis of (i) two graphs of the same web site crawled at consequent crawls (ii) sequence of graphs of the same web site crawled at consequent crawls. They key of the extension is to try to fix the positions of the (groups of) nodes that tend not to change over the crawls. Suggested milestones and objectives:
  1. Install and play with the walrus package
  2. Visualize available web archive data
  3. Visualize the archive web data sequentially
  4. Extend the visualization where both graphs are shown where differences are highlighted
  5. Show the visualizations of two consequent graphs in animation for consequent web graphs
  6. Improve the graph layouting for the consequent visualizations
  7. Implement a simple graph generator for control experiments