Volume 10, Issue 1 Articles Trott's Corner New Products New Publications Calendar News Bulletins New Resources Classifieds Download This Issue Editorial Policy Staff and Contributors Submissions Subscriptions Advertising Back Issues Contact Information 
Efficient, HighQuality ForceDirected Graph Drawing
3. ForceDirected AlgorithmsIn this section we present the basic forcedirected algorithms and analyze the characteristics of the layout given by the springelectrical model. We will propose a general repulsive force model, as well as an adaptive step control scheme. 3.1. Spring and SpringElectrical ModelsForcedirected 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 springelectrical 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 springelectrical 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 springelectrical 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 springelectrical 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 springelectrical 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 springelectrical model by finding the root of a system of equations (see equation (2)) using Mathematica's FindRoot function, instead of the usual forcedirected 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 springelectrical model. The reason for this distortion effect at the periphery is the strong longrange force that decays slowly as the distance increases. While typically this strong longrange 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 longrange repulsive force. However, too large a value of , thus too weak a longrange 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 springelectrical model. It can, however, suffer from its relatively weak repulsive forces (see Section 6.3). Furthermore, as discussed later, in the springelectrical model, the longrange 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 SchemeThe energy of both the springelectrical and the spring models can be minimized iteratively by moving the vertices along the direction of forces exerted on them. The following forcedirected algorithm iteratively minimizes the system energy, with and as defined in (1) or (5). The algorithm starts with a random, or usersupplied, initial layout. Algorithm 1. An iterative forcedirected 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 GaussSeidel 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 forcedirected 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 forcedirected algorithm. However, for an application of a forcedirected 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).


About Mathematica  Download Mathematica Player © Wolfram Media, Inc. All rights reserved. 