Sometimes social networks visualizations look so damn complicated. I at least tend to look at where the graph is busiest, and sort of intuitively conclude that that node is the most important one. There must be a better way, right?
Of course there is–why else would I pose such an obviously rhetorical question? (damn it. did it again).
So consider a hierarchical social network where there is a group of individuals at the lowest level, and a group at the highest. Typically a social network visualization would represent if, and how, those groups of people are related.
If we want to add more levels of relationships to the relationship, we visualize the adjacency of the graph, adding edges in a linear way. This, however, may become really, really cluttered really fast.
(Via Fms ASG Magazine)
Danny Holten, a postdoc at Eindhoven University of Technology, presents an awesome and aesthetically pleasing way of simplifying graphs and making tree graphs more accessible (.pdf here). What makes his project so useful, however, is how he outlines the particular thought process that goes into making a visualization.
(Use of Holten’s technique, in “Execution Trace Analysis Through Massive Sequence and Circular Bundle Views.” Available here)
Holten proposes “Hierarchical edge bundling” as a method of bundling those adjacency edges together. He draws an analogy to bundling your electrical wires together in order to reduce clutter, while fanning them out at their terminus in order to plus them in.
So what’s wrong with regular tree graphs?
Although radial and balloon layout techniques utilize the available space somewhat more efficiently than rooted layout techniques, nodelink representations do not make optimal use of the available space in general…However, using enclosure to display the tree structure makes it more difficult for viewers to perceive the hierarchical relationship between nodes (Holten 2006).
Examples of his problem trees:
(Awesome radial tree. The Reingold-Tilford tree layout algorithm in polar coordinates (as improved by Walker and Buchheim et al.), applied to the flare package hierarchy. Via Mike Bostock on flickr)
(Via Orbifold)
(Another treemap. Via quince)
Scott Marshal, in a survey of graph visualization (pdf here), proposes a fundamental set of issues:
The basic graph drawing problem can be put simply: given a set of nodes with a set of edges (relations), calculate the position of the nodes and the curve to be drawn for each edge. Of course, this problem has always existed, for the simple reason that a graph is often defined by its drawing. Indeed, Euler himself relied on a drawing to solve the “Königsberger Brückenproblem” in his 1736 paper (Marshall 2000).
However, Marshall points out that there is a difference between graph drawing and good graph drawing…and, “That is where the problem becomes more intricate: it requires the definition of properties and a classification of layouts according to the type of graphs to which they can be applied.”
So what does a good graph look like? Well, first we need to consider a few key factors. First is planarity (if you can draw a graph without edge crossings); but also aesthetic rules (even distribution of nodes and edges, &c.), size, predictability (two runs of the same algorithm need to have relatively similar visual results of the same graph), and time complexity (near real-time interaction with short update times).
Why (and how) trees? As Marshall notes, tree layout algorithms are simple and easy to implement (Walker 1990), so we should just look at how to construct efficient spanning trees. What that means is extracting all the nodes from a graph and constructing the tree contingent on those extracted nodes, adding edges to the tree afterward (Marshall 2000).
(Reproduced from Mutzel et al. 1998)
So what does Holten’s bundled graph look like? Pretty awesome.
Holten concludes that by using bundles, not only are graphs more accessible, but the creator can have more control over the amount of information, as well as the information level being presented:
Using the bundling strength b to provide a trade-off between low-level and high-level views of the adjacency relations. The value of b increases from left-to-right; low values mainly provide low-level, node-to-node connectivity information, whereas high values provide high-level information as well by implicit visualization of adjacency edges between parent nodes that are the result of explicit adjacency edges between their respective child nodes.
What I think social science can learn here is maybe a little obvious: if you can, simplify your information presentation. That does not mean presenting less data though! Holten demonstrates that by looking at the way data is presented, you can imagine new methods of visually encoding information that are not only more efficient than text, but radically different from the typical regression.
What may be a fundamental issue is that the ubiquitous (and often only partially useful) regression is used to prove a hypothesis to a particular audience that is used to only seeing regressions. Yes, the OLS regression is a powerful tool, but when it comes to spatial statistics or multilevel analysis, it can only tell part of the story. In a more interdisciplinary world, with greater access to information in all forms, Holten’s graphs are readable, accessible to a wider audience, and, more importantly, able to demonstrate a point usable in a wide variety of contexts.
(Thanks to VisualComplexity for introducing me to Holten’s work. It is an incredible site that I recommend anyone for a huge database of visualizations)
C. Buchheim, M. Junger, S. Leipert. 2002. Improving Walker’s Algorithm to Run in Linear Time. Graph Drawing 2002, LNCS 2528, pp. 344–353. Springer.
Holten, Danny. 2006. Hierarchical Edge Bundles: Hierarchical Edge Bundles. IEEE Transactions on Visualization and Computer Graphics 12(5).
Marshall, Scott, Ivan Herman, Guy Melancon. 2000. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE: 1-21.
P. Mutzel, C. Gutwengwer, R. Brockenauer, S. Fialko, G. Klau, M. Kruger, T. Ziegler, S. Naher, D. Alberts, D. Ambras, G. Koch, M. Junger, C. Bucheim, S. Leipert, 1998. A Library of Algorithms for Graph Drawing. Proceedings of the Symposium on Graph Drawing GD ’97 Symposium.
J. Q. Walker. 1990. A Node-positioning Algorithm for General Trees. Software Practice and Experience 20(7): 685–705.
The Reingold-Tilford tree layout algorithm in polar coordinates (as improved by Walker and Buchheim et al.), applied to the flare package hierarchy. Uses pv.Layout.tree.
Related Articles
- arbor.js – html5 graph visualization library (arborjs.org)
Seeing Complexity 
Matt
02/06/2011
I too was smitten by Holten’s work.
I keep my eye out for mentions, but I’m yet to find an implementation of the algorithm outside the paper.
Hoping someone will code something in Processing.
jacobalonso
02/06/2011
I did find one use, when I was researching this post– “Visual Support for Analyzing Network Traffic and Intrusion Detection Events using TreeMap and Graph Representations,” out of the University of Konstanz. I just see that in my notes, I’m not sure where it is online (maybe webofscience?).
One article that I did note the link for was:
Telea et al. 2009. Extraction and Visualization of Call Dependencies for Large C/C++ Code Bases: A Comparative Study. VisSoft09 Working Paper.
Telea et al. look software dependencies and lay out a method of visualizing call and hierarchy graphs for C++ programs. They utilize Holten (2006) in making those nice edge bundles when they visualize their links to nodes.
Columbus Tall
02/09/2011
I simply want to tell you that I am new to blogging and site-building and absolutely savored this web blog. Most likely I’m planning to bookmark your site . You definitely come with good writings. Thank you for sharing your blog site.