Component Binning: a network layout improvement in NodeXL v.108

Network visualizations can be very compelling but they are often a smear of unintelligible nodes and edges without refinement and filtering.  Creating an automated layout for a complex graph is a challenging area of mathematics and computer science.  Several layouts are available and are widely implemented, including the Fruchterman-Reingold layout, the Harel-Koren fast multilevel layout, and a number of geometric designs like circles, grids and trees that can be useful for some data sets.

Improvements to these layouts have been slow in coming: the math behind these layout algorithms have no simple or even best solutions.

Recently, a simple technique has done a great deal to improve many complex network graph layouts by arranging each component in the graph in a grid.  Components are pieces of a network that are not connected to any other component.  These islands come in various sizes, often there is one large or giant component and many smaller “isolates”.  In many layout algorithms these isolates are a problem and are either pushed to the edges of the graph into a circle or ellipse that resembles an “asteroid belt” (Fruchterman-Reingold) or are overlaid on top of all the other isolates (Haren-Koren).  A solution is to collect all the “isolates” and organize them sensibly and within a grid such that each component is laid out within its own territory or cell.

*BEFORE*

*AFTER*

The result is a step towards what Ben Shneiderman refers to as “NetViz Nirvana” – a state in which network graphs are more visually intelligible.  When isolates are binned in a grid, two graphs can be visually contrasted far more than when they each have a smeared “asteroid belt” of nodes.

We have implemented an initial binning layout method in the latest version of NodeXL that simply breaks out each component and places it within a grid based on the number of nodes and edges in that sub-graph.  I can imagine more sophisticated approaches would locate each sub-graph based on a range of attributes.

I think the improvement in network visualization is significant.  Isolates no longer impose a big effect on the giant component which often was compacted and compressed as a result of even a single isolate.