http://kmi.open.ac.uk/seminars/2982 Charting Collections of Connections in Social Media: Creating Maps and Measures with NodeXL This…
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.
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.
This Post Has 6 Comments
Do you describe an algorithm for layout a network with several disconnected components?
I think that ‘classical’ modification of force-directed scheme would produce better results.
We do not describe such an algorithm, although they are well documented: http://en.wikipedia.org/wiki/Force-based_algorithms
This approach is a hybrid: we still run the FR algorithm, we just keep each component in a separate layout space.
I agree, subgraph partitions make a lot of sense. I’ve used this before in 2 ways: binning as you have, but also hierarchical graph layout in which th graph of components is first laid out then each connected component.
Another useful thing to explore is the initial conditions prior to layout. This can get you quite a way to improvement.
[…] the graph and order them in neat rows at the bottom of the canvas. This feature was mentioned in a previous post, but finding the feature may not be […]
Hi Marc, I have just updated my NodeXL installation and the binning layout seems to have disappeared. Help! I was loving this feature.
Found solution to Binning in the Release History – please disregard.
Comments are closed.