What is a Force Directed Algorithm (Spring Algorithm)?Force directed algorithms view the graph as a virtual physical system, where the nodes of the graph are bodies of thesystem. 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 bemodeled as gravitational attraction and all nodes have anelectrical repulsion between them. It is also possible for thesystem to simulate unnatural forces acting on the bodies, whichhave no direct physical analogy, for example the use of alogarithmic distance measure rather than Euclidean . 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 totheir 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 time step, 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.
BackgroundThe 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 . 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 alocally 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.
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 thefollowing. Given an initial layout method, such as random placement, a graph can be assigned geometric attributes. Thisprocess creates a graph layout, which can be then be rendered toproduce a graph drawing. This is the classical graph drawing""pipe-line".
In the FADE paradigm, we take the graph layout andperform a geometric clustering (typically by recursive spacedecomposition) of the locations of the nodes. This process, alongwith 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 there computation of the hierarchical compound graph, which was formed on the previous locations. This process, if iterated, is calledthe 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 therepeat loop in the following:
UNTIL Stopping ConditionEND
- Compute Initial Layout
- 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)
- Move Nodes
- Update Bounding Area/Volume
Performance ImprovementThe 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 ahigh quality geometric clustering of the node positions, nor isit 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 ofhuge 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.[ Basic spring algorithm layout ] 8meg [ zipped ]
Images or Animations may not be used
without permission. Created: May 2000
Updated: July 25th 2010