Software Systems
Engineering Research Group
Department of Computer Science
BTU Cottbus
Graph layouts that reflect dense subgraphs (like communities in social networks, cohesive subsystems in software systems) and conform to graph clusterings.
Node-repulsion LinLog [1,2,4] and edge-repulsion LinLog [3, 4], two energy models (force models) for layouts that reflect the density structure of graphs (community structure of networks). Energy models are quality measures for graph layouts, and enable the automatic computation of layouts with energy minimization algorithms (force calculation algorithms, spring embedders). The layouts of both LinLog 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.
Graph layouts that minimize edge-repulsion LinLog energy are relaxations of, and thus consistent with, graph clusterings that maximize Newman and Girvan's widely used Modularity measure [6]. For example, the three main groups in the above LinLog layout of the world trade graph conform to the three Modularity clusters (indicated by colors); the layout shows more details than the clustering, for example that IRN or EGY belong neither clearly to the European group nor clearly to the East Asian group, and that there are smaller groups of closely interlocked countries like CHN and HKG, AUS and NZL, or GBR and IRL.
The open source program LinLogLayout with reusable Java classes (LGPL license) for computing LinLog layouts and Modularity clusterings.
LinLogLayout is a simple open-source program (written in Java) for computing graph layouts, using the LinLog energy models and standard energy models like Fruchterman-Reingold, and graph clusterings, using Newman and Girvan's Modularity measure. 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-level 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, including 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)
Author: Andreas Noack