An energy model specifies what is considered a good graph layout. Technically, an energy model is a function that maps layouts to numbers, which are interpreted as energy of the layout. For a given graph, a layout with high energy is considered worse than a layout with low energy. Thus computing a good layout means minimizing energy.
The minimum energy layouts of classical energy models (like the Fruchterman-Reingold model [1]) are not satisfactory for some important graph models of software systems, like call graphs. In call graphs (considered as undirected), the average path length between two nodes is very small (typically about 3 for a graph with 1000 nodes), and there are clusters of densely connected nodes.
To lay out call graphs and other graphs with similar properties, we designed the LinLog energy model. In minimum energy layouts of the LinLog model, different clusters are clearly separated and have interpretable distances. Proofs of these properties and more information about the LinLog energy model can be found in [2-5].
The following animations and pictures compare layouts of the LinLog energy model with layouts of the Fruchterman-Reingold model.
The graph has eight clusters with 50 nodes each. The clusters are completely connected (i.e. cliques, edge probability 1). For two nodes u, v belonging to different clusters, the probability of the edge {u,v} is 0.2. The left animation shows layouts of the LinLog energy model: the initial random layout and the layouts after 3, 6, 9, ..., 60 iterations of the energy minimization algorithm. The right picture shows the layout of the Fruchterman-Reingold model after 60 iterations.
The graphs has one central cluster of 200 nodes and three clusters of 100 nodes each, called cluster A, B and C. The probability of an edge {u,v} is
The left animation shows layouts of the LinLog energy model: the initial random layout and the layouts after 3, 6, 9, ..., 60 iterations of the energy minimization algorithm. The right picture shows the layout of the Fruchterman-Reingold model after 60 iterations.
[1] Thomas M. J. Fruchterman and Edward M. Reingold: Graph Drawing by Force-Directed Placement. Software - Practice and Experience 21(11): 1129-1164, 1991
[2] 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)
[3] 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)
[4] 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)
[5] Andreas Noack. Energy Models for Graph Clustering. Journal of Graph Algorithms and Applications 11(2):453-480, 2007. (Abstract, PDF, Publisher)
Author: Andreas Noack