3. Force-Directed Algorithms

In this section we present the basic force-directed algorithms and analyze the characteristics of the layout given by the spring-electrical model. We will propose a general repulsive force model, as well as an adaptive step control scheme.

3.1. Spring and Spring-Electrical Models

Force-directed algorithms model the graph layout problem by assigning attractive and repulsive forces between vertices and finding the optimal layout by minimizing the energy of the system.

The model of Fruchterman and Reigold [4], which we refer to as the spring-electrical model, has two forces. The repulsive force, , exists between any two vertices and and is inversely proportional to the distance between them. The attractive force, , on the other hand, exists only between neighboring vertices and is proportional to the square of the distance

The combined force on a vertex is

In these formulas, is a parameter known as the optimal distance [4], or natural spring length [2]. The parameter regulates the relative strength of the repulsive and attractive forces and was introduced in [2]. It is easy to see that for a graph of two vertices linked by an edge, the force on each vertex diminishes when the distance between them is equal to . The total energy of the system can be considered as

where is the vector of coordinates, .

From a mathematical point of view, changing the parameters and does not actually change the minimal energy layout of the graph but merely scales the layout, as the following theorem shows.

Theorem 1. Let minimizes the energy of the spring-electrical model , then minimizes , where . Here and are all positive real numbers.

Proof: This follows simply by the relationship

where . Thus,

Even though the parameters and do not have any bearing on the optimal layout from a mathematical point of view, from an algorithmic point of view, if an iterative algorithm (see Algorithm 1) is applied to minimize the energy from an initial layout, choosing a suitable or to reflect the range of the initial position will help the convergence to the optimal layout. Throughout this article, unless otherwise specified, we fix as in [2], but vary for this purpose.

One intrinsic feature of graph drawings by the spring-electrical model is that vertices in the periphery tend to be closer to each other than those in the center, even for a uniform mesh. We call this the peripheral effect. For example, Figure 1 shows a mesh of 100 vertices laid out using the spring-electrical model, with vertices near the outside boundary clearly closer to each other than those near the center.

Figure 1. A regular mesh laid out using the spring-electrical model. This graph and the others in this article were drawn with the Mathematica GraphPlot command, which is discussed in Section 6.

This peripheral effect is more profound for graphs with large diameter. We studied this effect for a line graph, with 100 vertices linked in a line. The vertices are numbered 1 to 100, with vertex 50 and 51 in the middle of the line. We find an accurate layout under the spring-electrical model by finding the root of a system of equations (see equation (2)) using Mathematica's FindRoot function, instead of the usual force-directed iterative algorithm, because the latter is far less accurate. We set the parameters and Theorem 1 shows that the exact values of these two parameters are not important.

Figure 2 shows the distribution of edge lengths. As can be seen, the edge lengths of the 99 edges vary from 4.143 at the middle to 1.523 at the sides, with the ratio of the longest length to the shortest .

Figure 2. Distribution of edge lengths for a line graph of 100 vertices and 99 edges, laid out using the spring-electrical model.

The reason for this distortion effect at the periphery is the strong long-range force that decays slowly as the distance increases. While typically this strong long-range force does not interfere with the aesthetics of the layout, some applications, such as tree graphs, tend to suffer more. For these classes of graphs, the following general repulsive force model can be used.

The larger the parameter , the weaker the long-range repulsive force. However, too large a value of , thus too weak a long-range force, could cause the graph that should be spread out to crease instead. We found that works well. Figure 3 shows the peripheral effect against the size of the line graph, for both the general model (4) with and , and the Fruchterman and Reigold force model (1), which corresponds to the general model with . As can be seen, the general model with reduces the peripheral effect significantly.

Figure 3. A plot of the ratio between the largest and smallest edge lengths for line graphs of size 3 to 100 vertices.

In the force model of Kamada and Kawai [7], which we will refer to as the spring model, springs are attached between any two pairs of vertices, with the ideal length of a spring proportional to the graph distance between these two vertices. Thus both the repulsive and attractive forces are expressed as

and the spring energy is

The spring model does not suffer from the peripheral effect of the spring-electrical model. It can, however, suffer from its relatively weak repulsive forces (see Section 6.3). Furthermore, as discussed later, in the spring-electrical model, the long-range force between all vertices can be well approximated by grouping vertices together using the octree/quadtree technique. This is, however, not possible in the spring model.

3.2. An Adaptive Cooling Scheme

The energy of both the spring-electrical and the spring models can be minimized iteratively by moving the vertices along the direction of forces exerted on them. The following force-directed algorithm iteratively minimizes the system energy, with and as defined in (1) or (5). The algorithm starts with a random, or user-supplied, initial layout.

Algorithm 1. An iterative force-directed algorithm.

In the algorithm, is a termination tolerance. The algorithm stops when a change in the layout between subsequent iterations is less than

As in [2], we update the layout of a vertex as soon as the force for this vertex is calculated, instead of waiting until forces for all vertices have been calculated. This improves the convergence of the iterative procedure, much like the fact that among stationary iterative linear system solvers, the Gauss-Seidel algorithm is often faster than the Jacobi algorithm.

In Algorithm 1, it is necessary to update the step length . The "cooling schedule" used in most expositions (e.g., [19]) of force-directed algorithms allows large movements (large step length) at the beginning of the iterations, but the step length reduces as the algorithm progresses. Walshaw [2] used a simple scheme,

with . We found this to be adequate in the refinement phase of a multilevel force-directed algorithm. However, for an application of a force-directed algorithm from a random initial layout, an adaptive step length update scheme is more successful in escaping from local minimums. This adaptive scheme is motivated by the trust region algorithm for optimization [20], where step length can increase as well as reduce, depending on the progress made. Here we measure progress by the decrease in system energy.

In the preceding algorithm, is a static variable that is initialized to zero and parameter . The idea of this algorithm is that the step length is kept unchanged if energy is being reduced and increased to if the energy is reduced more than five times in a row. We only reduce the step length if energy increases.

Compared with the simple step length update scheme (6), the adaptive scheme is much better in escaping from local minimums. Figure 4 shows the result of applying 70 iterations of Algorithm 1 to the jagmesh1 graph with 936 vertices from MatrixMarket (math.nist.gov/MatrixMarket). The adaptive scheme is clearly much better and is able to untangle the graph a lot further than the simple scheme.

Figure 4. Comparing adaptive and simple step length update schemes on jagmesh1 after 70 iterations: simple scheme (left); adaptive scheme (middle); what the layout should look like (right).