Software Systems
Engineering Research Group
Department of Computer Science
BTU Cottbus
Graph drawings that reveal graph structure: clearly separated clusters, interpretable distances between the clusters.
Drawings of undirected graphs are computed using energy-based methods (also called force-directed methods, spring embedders). Energy-based methods have two parts: an energy model, and an algorithm that searches a state with minimum total energy. Our main results are two energy models whose minimum energy drawings reveal the cluster structure of the drawn graph: the node-repulsion LinLog model [1,2], and the edge-repulsion LinLog model [3]. An implementation of an energy minimization algorithm is available in the Downloads section.
In both energy models, adjacent graph nodes (i.e. nodes that are connected by an edge) attract. The models differ in the repulsion: In the node-repulsion LinLog model, nodes repulse, while in the edge-repulsion LinLog model, edges repulse. The drawings of both models are similar if all nodes of the graph have approximately the same degree (i.e., number of edges), but for graphs with nonuniform degrees (like power law graphs), only edge-repulsion LinLog avoids dense accumulations of nodes with high degrees.
For introductory information on graph drawing (including energy-based methods) see the standard textbook: Giuseppe Di Battista, Peter Eades, Roberto Tamassia and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
LinLogLayout is a simple, easy-to-use open source program (written in Java) for computing graph drawings, using the LinLog energy models and standard energy models like Fruchterman-Reingold, and graph clusterings, using the Modularity measure of Mark Newman. It includes a reusable energy minimizer (spring embedder) class based on the efficient Barnes-Hut algorithm, and a reusable class for Modularity clustering based on a multi-scale algorithm.
[6] Andreas Noack. Modularity Clustering is Force-Directed Layout. Preprint arXiv:0807.4052, 2008. (Abstract, PDF)
[5] Andreas Noack. Unified Quality Measures for Clusterings, Layouts, and Orderings of Graphs, and Their Application as Software Design Criteria. PhD Thesis, Brandenburgische Technische Universität Cottbus, 2007. URN: urn:nbn:de:kobv:co1-opus-4046. (Electronic Publication (includes PDF and Abstract))
[4] Andreas Noack. Energy Models for Graph Clustering. Journal of Graph Algorithms and Applications 11(2):453-480, 2007. (Abstract, PDF, Publisher)
[3] Andreas Noack. Energy-Based Clustering of Graphs with Nonuniform Degrees. In Proceedings of the 13th International Symposium on Graph Drawing (GD 2005), LNCS 3843, pages 309-320. © Springer-Verlag, 2006. (Abstract, PDF, Publisher)
[2] Andreas Noack. An Energy Model for Visual Graph Clustering. In Proceedings of the 11th International Symposium on Graph Drawing (GD 2003), LNCS 2912, pages 425-436. © Springer-Verlag, 2004. (Abstract, PDF, Publisher)
[1] Andreas Noack. Energy Models for Drawing Clustered Small-World Graphs. Technical Report 07/03, Computer Science Reports, Brandenburg University of Technology at Cottbus, 2003. (Abstract, PDF)