Graph Layout

Abstract

As Networks and their structure have become a major field of research a strong demand to visualize these networks has emerged. We address this challenge by formalizing the well established spring layout in terms of dynamic equations. We thus opening up the design space for new algorithms. Drawing from the knowledge of systems design, we derive a layout algorithm that remedies several drawbacks of the original spring layout. This new algorithm relies on the balancing of two antagonistic forces. We thus call it ARF for "attractive and repulsive forces''. It is, as we claim, particularly suited for dynamic layout of smaller networks. We back this claim with several application examples from on going complex systems research.

Publication

Markus M. Geipel: Self-Organization applied to Dynamic Network Layout
(paper submitted, available on arXiv:0704.1748)

Demonstrations

See the demonstration page >>

The following video shows ARF at work. It addapts the layout to the constantly changing graph topology: demo.mpg

ARF was also used to visualize results in the field of innovation network research. The videos show simulations of the evolution of R&D cooperations between firms. They were presented on the WEHIA 06 conference. For more details on the simulations, see the innovation networks page >>

James Glattfelder produced a fancy 3D fly though video posted on YouTube. Watch it here >>

The following graph shows class dependencies in an open source java project (circa 2500 classes). One layout was generated with neato and the other one with ARF (graph data: software.dot). If you achieve better layout results with neato then the one presented here, please let me know. In this case, I will gladly update the page.

Cuttlefish

The graphlayout lead also to a SourceForge project >>

Downloads

To make our results reproducible we provide the following dowloads:

• example layout in pdf-format: software dependencies in color
• dot files: dotfiles.zip
  The zip file contains all the dot files of the sample graphs, as well as a shellscript to layout them with all layouters available in graphviz.
• java source: netbrowser.jar,
  This archive includes an implementation of the ARF Layouter for the JUNG Framework. See Layout Applet for an example how to use layouts in JUNG.
  The archive also containes a prototypical implementation of the network browser mentioned in the paper.

How to run the browser
Add the jar file to your classpath and start the browser as follows:

java ch.ethz.sg.arf.netbrowser.NetworkBrowserFrame

The browser starts with an arbitrary random network. If you want to browse your own networks, just write a class that extends the ANetModel class. This way, you can plug any data source into the browser. See the comments in the code for details. To load your network, use the following command:

java ch.ethz.sg.arf.netbrowser.NetworkBrowserFrame YourNetModelClass StartNodeId

Please note, that the network browser and the ARF implementation are prototypical implementations. They are meant as a proof of concept and nothing more. However, you are free to use and extend the code unter the GNU General Public License as published by the Free Software Foundation.

Contact

Markus M Geipel