Graph Layout II
From CS294-10 Visualization Sp11
Lecture on April 13, 2011
Same readings as last time. Read something you didn't read for Monday's class. You should still make a new comment for this lecture
- Graph Visualization and Navigation in Information Visualization: A Survey. Ivan Herman, Guy Melancon, M. Scott Marshall. IEEE Transactions on Visualization and Computer Graphics, 2000. Just skim this one.(pdf)
- Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data. Danny Holten. InfoVis 2006. (pdf)
- Improving Walker's Algorithm to Run in Linear Time. Buchheim, Jünger, and Leipert. Graph Drawing 2002. (pdf)
- Dig-cola: Directed graph layout through constrained energy minimization. Tim Dwyer and Yehuda Koren. IEEE InfoVis 2005. (pdf) [Note: This won the best paper award at InfoVis 05.]
- Vizster: Visualizing Online Social Networks. Jeffrey Heer, danah boyd. InfoVis 2005. (pdf)
- Visual Exploration of Multivariate Graphs. M. Wattenberg. CHI 2006. (pdf)
- A Technique for Drawing Directed Graphs. Gansner, Koutsofios, North, Vo. 1993. (pdf) [Note: This covers the DOT algorithm, used by the popular GraphViz package]
Demonstrations / Examples
- GraphViz - popular graph layout package
- Tulip - a C++ library for large graph layout and visualization
- Java Universal Network/Graph Framework - Java graph processing and visualization library
- prefuse visualization toolkit - Java information visualization toolkit supporting interactive visualization of graphs and trees
Michael Porath - Apr 13, 2011 03:58:32 pm
Eyebeam, Google, and GAFFTA organized a visualization challenge that has caused some buzz in my twitter stream. The challenge is about visualizing recent budget and tax data. Many visualizations took a different approach to the tree that is the breakdown in budget figures. Some examples use tree maps, others use spanning trees or stream graphs. I personally found http://datavizchallenge.org/viz/68 to be an effective visualization because it dedicates most screen real estate to the figures you're looking at.
Make sure to visit "all entries", not the finalists visualization. The jury didn't necessarily choose the most effective visualizations. http://datavizchallenge.org/explore
Julian Limon - Apr 13, 2011 05:49:46 pm
I agree with was said in class today about Treemaps. I find them unintuitive and confusing in most cases. It's not that I think they aren't useful--I believe that they may convey a general overview in cases where fast decisions must be made (such as the stock market example and the case that Michael Cohen mentioned in class). However, in many cases they are created without justification. They certainly look more impressive than a bar chart, but that doesn't make them more effective.
On a different note, I was intrigued by the concept of degree-of-interest trees. They might be useful for a number of situations where there is a tradeoff between details and context. Trying to infer what the right interest is may be difficult, though. Even if the system learns from the most common cases, the default visualizations may prime the user to a certain analysis. If the user doesn't go ahead and discover her own path, she might miss the opportunity to discover some other interesting aspects of the data.
Michael Hsueh - Apr 14, 2011 12:35:35 am
Vizster is a neat system that visualizes social network graphs. One thing I've noticed about several of the graph visualization tools we've seen so far in the class is that they frequently use physical analogies to model how to visualize things. For example, in the Vizster system, the concept of a spring is used to model how far nodes and clusters should stay from each other. The analogy does not stop there as the spring model is also useful in interaction. The Vizster system simulates nodes returning back to their positions, with the system "bobbing" and contracting back into equilibrium, just as a network of springs would. The Holten paper talks about splines that are organized into bundles that can be splayed out. Our physical world knowledge of bundles of wires carries over into the more abstract domain of visualizations. Specifically, our knowledge of real world bundles translate conceptually into how we understand relationships between the elements depicted in the visualizations (e.g., wires connect individual components, while bundles of wires connect higher level devices). Physical world analogies seem to work effectively in the context of graph visualization.
Overall, I really like the Vizster system. It seems very well designed. Something that would have been cool is if there was a way to recursively find clusters within clusters.
Saung Li - Apr 14, 2011 06:30:46 pm
With the explosion of social networking services, systems like Vizster can help us study the large amount of data that has arisen from these services. I would like to see Vizster integrated with a site like Facebook so that people can explore how they are related to others. I find the X-ray mode to be a pretty cool way to see the attributes of others; it colors in the names of people and the actual color correlates to the value of the attribute. I disagree with the colors chosen though, as the black background and bright colors create an unpleasant sight. The Herman paper raises a good point on how zooming and panning can make the user lose context. When exploring a road network, for example, a user might have to keep zooming in and out and panning to look at different places and keep track of where he currently is observing. One of the focus and context techniques is the fisheye distortion, where part of the grid can be blown up. This is an interesting way to deal with the problem of losing context, but it may just look weird.
Matthew Can - Apr 15, 2011 05:06:51 am
I was fascinated by the exotic visualizations produced by Holten's hierarchical edge bundling. The method not only reduces visual clutter but also highlights the connectedness of nodes in the hierarchy graph through the bundling of adjacency edges between their children. I think it would be interesting to explore ways that interaction can enhance this visualization. The paper mentions this somewhat, but I think it deserves greater emphasis. For example, the brushing technique could be extended to support multiple selections, assigning different colors to each one. This would help resolve the ambiguity problem when several bundles overlap.
Brandon Liu - Apr 15, 2011 03:56:35 pm
In class, we discussed some of the problems with TreeMaps. I found that color works pretty well to distinguish the depth of an area; For example the file system visualization SpaceMonger uses a continuous range to show how deep something is http://www.sixty-five.cc/sm/ : of course, if you indicate depth with color, you also lose the use of color to encode another dimension.
Siamak Faridani - Apr 18, 2011 04:38:29 am
I enjoyed Herman et al's paper. It was an interesting collection of examples and the brief explanation for each type of visualization was useful. Although I am not sure if the ghosting, hiding and grouping method that is detailed in page 16 is intuitive enough for me. I didn't know anything about the journals and conferences in this field so the last section was very educational.
Karl He - Apr 18, 2011 05:07:23 am
The Dig-CoLa algorithm exhibits some pretty dramatic improvements over standard drawings of directed graphs. It seems to accomplish this by going beyond a simple recursive algorithm, and imposing many conditions upon the graph as a whole. I particularly like the concept of the bands to retain the idea of one axis being heirarchical information, keeping the graph easy to parse.
Sally Ahn - Apr 18, 2011 06:01:57 am
Dwer and Koren describe how force-directed placement algorithms, which had been popular for undirected graphs, can also be applied to directed graphs to greatly improve their layout. Their Dig-CoLa algorithm does this by imposing hierarchy constraints on node clusters and positioning them by minimizing the stress function so that these constraints hold. I thought this was a great way to overcome some of the problems they illustrate in the paper (e.g. cyclic vertices in the same level that get "squeezed" into a single line). I also really liked their use of hierarchy bands to group the nodes in the same level. I think some visual aids (e.g. pale background colors corresponding to the level) would have helped to map the nodes that are farther from band for their simpler examples (Fig. 4), but it would be too distracting for complicated examples with many levels (Fig. 6). Nevertheless, the complicated examples clearly demonstrate how valuable their method is for directed graph visualizations: by encoding hierarchical information with the position of the nodes, they remove the need for arrows in the links, which removes a huge amount of clutter.