NOTE: This page relates to older visualization work 99-02, during my PhD. I have now returned to work in this field with my new postdoc and PhD students in UCD Ireland. We are exploring larger scale layouts, personalised layout, visualisation for software engineers and comparative visualisation techniques in a pervasive computing environment. Please follow this link to see more on this new research and publications.
What is a Force Directed Algorithm (Spring Algorithm)?
Quick answer: Please see the following series of animations. (link)Force directed algorithms view the graph as a virtual physical system, where the nodes of the graph are bodies of the system. These bodies have forces acting on or between them. Often the forces are physics-based, and therefore have a natural analogy, such as magnetic repulsion or gravitational attraction. See for example this series of images which show a graph drawing from a random layout to the final aesthetically pleasant drawing of the graph. The general idea behind force directed layouts is explained here but we focus on the use of force directed algorithms for drawing large graphs. Figure 1 shows the drawing of a large graph produced by the FADE2D algorithm described below. Unlike the original algorithm which is order N squared per time step, FADE algorithms are order N log N per time step. (this means you can layout large graphs interactively using this algorithm, rather than waiting hours or days for the layout to compute)
Figure 1: An example drawing produced by the fast FADE2D drawing algorithm of a Type Compsite View of the source code from the Mosaic browser
Here for example in Figure 2, the edges can be modeled as gravitational attraction and all nodes have an electrical repulsion between them. It is also possible for the system to simulate unnatural forces acting on the bodies, which have no direct physical analogy, for example the use of a logarithmic distance measure rather than Euclidean [1]. This animation of a basic spring algorithm layout should give a clear idea of intuition behind such algorithms.
Figure 2: A graph drawing through a number of iterations of a force directed algorithm.
Regardless of the exact nature of the forces in the virtual physical system, force directed algorithms aim to compute a locally minimum energy layout of the nodes. This is usually achieved by computing the forces on each node and iterating the system in discrete time steps. The forces are applied to each node and the positions are updated accordingly. Force-directed algorithms are often used in graph drawing due to their flexibility, ease of implementation, and the aesthetically pleasant drawings they produce. However, classical force directed algorithms are unable to handle larger graphs due the inherent N squared cost at each tim estep, where N is the number of bodies in the system. This is a common problem and has prohibited the practical use of force directed algorithms for even moderately sized graphs of a few hundred nodes. The FADE layout paradigm, overcomes this computational limitation to allow large graphs to be drawn and abstractly represented [2, 3,4].
Background
The simulation of a virtual physical system for object placement pre-dates the development of force directed algorithms for graph drawing (Quinn 79). Given that it is NP-hard to draw a graph so that all edge lengths are the same, Eades first proposed a heuristic algorithm for drawing undirected graphs in two dimensions, based on simulating a virtual physical model [1]. This model is now referred to as the ""spring model", since each node is modeled as a steel ring with springs replacing the edges. In this model non-adjacent nodes repel each other according to an inverse square law. Given an initial random layout, the springs and the repulsive forces move the system to a locally minimal energy state, that is, an equilibrium configuration, which is then drawn. Eades noted that in such an equilibrium configuration, all the edges typically have relatively uniform length and nodes not connected by an edge are drawn far apart.
FADE Paradigm
A Spring Algorithm for the large scale layout and multi-level viewing of graphs
Figure 3: Multi-level viewing of Gd on two different levels of abstraction, from the hierarchical compound graph model.
The main idea of the FADE paradigm is the following. Given an initial layout method, such as random placement, a graph can be assigned geometric attributes. This process creates a graph layout, which can be then be rendered to produce a graph drawing. This is the classical graph drawing ""pipe-line".
In the FADE paradigm, we take the graph layout and perform a geometric clustering (typically by recursive space decomposition) of the locations of the nodes. This process, along with implied edge creation, forms a hierarchical compound graph.
Figure 4: Hierarchical Compound Graph, with edges, implied edges, clusters and the inclusions tree. (This example based on a quad tree decomposition of space)
The hierarchical compound graph, which includes the decomposition tree, allows us to approximate the nonedge forces in our force directed graph drawing algorithms. Using the decomposition tree, FADE computes forces; the nonedge forces may be approximately computed. After computing the forces, the underlying graph layout is updated, and this in turn requires the recomputation of the hierarchical compound graph, which was formed on the previous locations. This process, if iterated, is called the progressive cycle where as the graph drawing improves, so does the quality of the hierarchical compound graph.
Figure 5: Determing if a group of nodes in the decomposition is "far enough" away to be considered a pseudo-node in the force computation. (Based on MINd S/MINd < Theta)
Roughly speaking, the progressive cycle of FADE proceeds as the repeat loop in the following:
- Compute Initial Layout
- REPEAT
- Compute Edge Forces
- Construct Geometric Clustering
- FOR each node V
- Compute Approximate Nonedge Forces on V (walk the decomposition tree testing if each internal node is "far enough" away to be considered an approximation for the graph nodes it represents)
- ENDFOR
- Move Nodes
- Update Bounding Area/Volume
Performance Improvement
The performance improvement in the FADE paradigm comes from computing forces using a recursive decomposition of the locations of the nodes of a graph drawing, rather than all the nodes directly. Different decompositions generate recursive geometric clusterings of the nodes of the graph. The recursive clustering, represented as sub-trees, does not directly produce a high quality geometric clustering of the node positions, nor is it necessarily a high quality graph theoretic clustering. However the clustering does facilitate a dramatic improvement in the performance of force directed algorithms. Further, it allows for multi-level viewing of huge graphs at various levels of abstraction. Finally, as the quality of the drawing improves (as it reaches a lower energy state of the force system), the quality of clustering, exhibited by the decomposition tree, improves to a reasonable amount. This clustering, if it is of sufficient quality is appropriate for visual abstraction.[ 100-node 2D layout animated ] 17meg [ zipped ]
[ 1024-node 2D layout animated ] 16meg zipped
Examples in Three Dimensions using FADE3D
These graphs have been drawn using the 3D-FADE algorithm implemented in a prototype graph drawing application. The graphs or clustered graphs are then output in VRML format for rendering and stereoscopic viewing. The images from 45 to 3825 nodes are output from TGS 3Space Assistant and the animations are generated from Jasc Animation Shop The larger graphs have been rendered with POV-RAY after being converted to .pov format with vrml2pov.If you are not sure if your browser or system has the ability to view VRML files then look at the .gif or .avi animations, these should give you a good indication as to the shape of the graphs and the scale of the graphs these algorithms can handle. Or you can just try a simple test by viewing this small VRML model.
Home
