Wednesday, February 6, 2013

BioFabric: Combing the Lines Out of Hairballs!

It was not long ago that I officially proclaimed the start of my graph visualization journey on this blog. Two days into this analytic expedition of sorts I have already come across a branching path in the graph visualization world. One sign is pointing me to the chaotic land of hairballs, visualization cowboys darting back and forth to catch the nasty buggers with their algorithm loops. To the other path I see a sign pointing to a rather different sight, a land in which all species of hairball have gone extinct. In the fields of this unusual land I see what appear to be delicately woven tapestries floating about in space. What is this new breed of graph creature and where could it have possibly come from? 

As it turns out, deep down these tapestries are the same as the hairballs of the first branch's wild wild west. About a year ago a new cowboy came into town, bringing a rather different set of tools to help with the hairball infestation. Hairballs straying too close to the other side of the path are bound to meet defeat. Looking through the cowboy's set of tools you won't find the usual assortment of loop lassos and heuristics ammunition. No. Instead you will find a comb with the word BioFabric written over the handle. 

What is this BioFabric? BioFabric I have found out is a Java-based tool for the visualization of networks. Even those with only a brief exposure to graph visualization will find a plethora of tools throughout the Internet with different algorithms and capabilities for solving their complex data drawing problems. So,..., what makes BioFabric so different? What makes this cowboy stand out from the rest? What's the deal (in Jerry Seinfeld voice) with my unusually fluffy writing and short story-like introduction? I will say one word: lines! 

Now all of us graphsters and graphistas (males and females who like graph theory)are used to seeing lines for edges when we look at graphs. What I'm talking about are not edges though, but vertices. Rather than having the picture be made up of dots and lines we have lines and lines; specifically the vertices get drawn as horizontal lines and the edges between become vertical lines. Don't get it? Here I've made a few small examples showing what a few graphs drawn according to the traditional approach would look like if given the lines against lines treatment. 
The first example is the simplest of them all. We're just visualizing the graph of one dot (or K1 to be correct in graph lingo) as a horizontal line. What about the graph of two dots with a line in between (i.e. K2)? That will end up looking kind of like an I. The third graph which is the first cycle of the bunch (and K3 incidentally) will look kind of like a wind-chime after straightening things out (yeah...lame joke :-P). 

With those simple examples you should now have a slightly clearer idea of what I mean when I say graphing lines against lines. But these examples are small potatoes. If we are looking at graphs of this size or ones that are relatively small to the hairballs that I keep talking about, then the traditional approach would probably be a lot clearer to understand and eyeball for analysis. However, the focus of the last so many graph theory posts have not been about looking at these "small" manageable graphs, but rather the really scary monstrosities that have been replicating at an alarming rate in the land of hairballs. Those are the kinds of graphs that really benefit from the BioFabric treatment. The real power of BioFabric approach comes from the fact that your vertices become horizontal lines that can be of ANY length. Because said vertices can be as long as they wish, you won't have to worry about those horrid edge crossings anymore! If adding another edge to the graph runs the risk of introducing crossings to your visualization, just make the vertex longer and tack new edges to the end of it. The idea is that simple! 

Of course we've all been told time and time again that the devil is in the details, and some of you may be suspicious that this simple idea is too good to be true when you try to think how to organize the vertical and horizontal edges throughout this graphical mesh. If you do a little bit of reading up though (reference paper shown below) you will see that there is a very clear and systematic approach taken for this kind of layout scheme. So for my analytically minded readers who are not satisfied with just hearing that something is good without knowing why, I assure you that there is order and method that cleverly does the work just described. 

Now I have just been introduced to this new concept of graph visualization which is pretty ground shaking for me, the graph drawing traditionalist who always imagined vertices as dots. I am not a close-minded person though and find this new approach to be intriguing, interesting, and definitely promising! I plan on exploring this topic further and comparing it with the many vertex as dots approaches and see what kind of differences I find between the two general methods. I strongly encourage all of you to read up more on BioFabric's take on graph visualization. At the bottom I have provided links to the website of BioFabric and to a paper discussing the basic ideas behind it (it even talks about all of those darn details I was just telling you about!) Enjoy! 


Short Story Afterword: 

Long ago people were frightened at the possibility of the earth being round. It's not round! It's supposed to be flat! Hundreds of years later it appears that we have now reached a somewhat similar phase in history. I can hear the graphsters and graphistas saying: "Those vertices aren't supposed to be flat! They're round I say! Round!". Do you ever get the feeling of deja vu? (in Groundhog Day voice) :-) 

Link to BioFabric website:

Link to paper discussing BioFabric: