5. The Multilevel Algorithm

While approximation of long-range force using octree data structure greatly reduces the complexity of Algorithm 1, it does not change the fact that the algorithm repositions one vertex at a time, instead of laying out a whole region as a unit. Large graphs typically have many local minimal energy configurations, and such an algorithm is likely to settle to one of the local minimums. The adaptive step length control scheme we introduce goes some way toward a better layout, but as Figure 4 shows, is still insufficient toward a global minimum.

The multilevel approach has been used in many large-scale combinatorial optimization problems, such as graph partitioning [11, 12, 23], matrix ordering [24], the traveling salesman problem [25], and has proven to be a very useful meta-heuristic tool [26]. The multilevel approach was also used in graph drawing [2, 13, 14]. In particular, Walshaw [2] was able to lay out graphs with up to 225,000 vertices in a few minutes, and largely of good quality.

The multilevel approach has three distinctive phases: coarsening, coarsest graph layout, and prolongation and refinement. In the coarsening phase, a series of coarser and coarser graphs, , are generated. The aim is for each coarser graph to encapsulate the information needed to lay out its "parent" while containing fewer vertices and edges. The coarsening continues until a graph with only a small number of vertices is reached. The optimal layout for the coarsest graph can be found cheaply. The layouts on the coarser graphs are recursively prolonged to the finer graphs, with further refinement at each level. Hereafter, we use a superscript to denote the level. For example, is the coordinates of vertices in the level graph ,

5.1. Graph Coarsening

There are a number of ways to coarsen an undirected graph. One frequently used method is based on edge collapsing (EC) [11, 12, 23], in which pairs of adjacent vertices are selected and each pair is coalesced into one new vertex. Each vertex of the resulting coarser graph has an associated weight, equal to the number of original vertices it represents. Each edge of the coarser graph also has a weight associated with it. Initially, all edge weights are set to 1. During coarsening, edge weights are unchanged unless both merged vertices are adjacent to the same neighbor. In this case, the new edge is given a weight equal to the sum of the weights of the edges it replaces. The edges to be collapsed are usually selected using maximal matching. This is a maximal set of edges, no two of which are incident to the same vertex. For undirected graph partitioning, heavy-edge matching has been found to work well. Here, the idea is to preferentially collapse heavier edges. When looking through a neighbor list for an unmatched vertex, an edge with the largest weight is selected. In the context of graph drawing, Walshaw [2] chose to keep vertex weights in the coarser graphs as uniform as possible by matching a vertex with a neighbor with the smallest vertex weight. We found that both heavy-edge matching and matching with a vertex of smallest weight give graph layouts of similar quality and used the former in this article. Figure 6 illustrates a graph (left) and the result (middle) of coarsening using EC.

Other coarsening methods have been proposed. In [27], a maximal independent vertex set (MIVS) of a graph is chosen as the vertices for the coarser graph. An independent set of vertices is a subset of the vertices such that no two vertices in the subset are connected by an edge in the graph. An independent set is maximal if the addition of an extra vertex always destroys the independence. Edges of the coarser graph are formed by linking two vertices in MIVS by an edge if their distance apart is no greater than 3. Figure 6 illustrates a graph (left) and the result (right) of coarsening using MIVS.

Figure 6. An illustration of graph coarsening: original graph with 788 vertices (left); a coarser graph with 403 vertices resulted from EC (center); a coarser graph with 332 vertices resulted from MIVS (right).

We have implemented both EC and MIVS coarsening schemes for our multilevel graph drawing algorithm. Notice that with EC, the coarse graph always has more than 50% of the vertices of the original graph. For graphs with a high average degree, it may happen that the number of vertices in the coarser graph, , may be very close to the number of vertices in the original graph, . This can significantly increase the complexity of the multilevel algorithm. Therefore, we will stop coarsening if there are only two vertices in the graph or

We used . Here is the vertices in .

On the other hand, for a connected graph, the MIVS coarsening usually, though not necessarily, results in a coarser graph with less than 50% of the number of vertices of the original graph. In our experience, for graph layout, EC tends to give slightly better results than MIVS, probably because it coarsens less aggressively. However, MIVS is usually faster, due to the lower complexity. To overcome the complexity issue of EC, we propose a third scheme, HYBRID. This scheme uses EC whenever possible, however, if the threshold (9) is breached, we use MIVS coarsening instead.

5.2. Initial Layout on the Coarsest Graph

On the coarsest level, we lay out the graph using Algorithm 1 combined with the adaptive step length control scheme. For MIVS and HYBRID coarsening schemes, the coarsest graph has only two vertices, thus a random placement of the two vertices would be sufficient.

5.3. The Refinement Step

The layouts on the coarser graphs are recursively prolonged to the finer graphs, with further refinement at each level.

If graph was derived using EC from , the position of a vertex is given to the two vertices that collapse into . If was derived using MIVS from , then a vertex either inherits the position if it is in the MIVS, or must have one or more neighbors in MIVS, in which case the position of is the average of the positions of these neighbors.

Once the prolongation is carried out to give an initial layout for , this layout is refined using Algorithm 1. As in [2], if in the initial layout two vertices happen to be at the same position, as could be the case with EC-based coarsening, a random perturbation is done to separate them. Because the initial layout is derived from the layout of a coarser graph, this layout is typically already well placed globally and what is required is just some local adjustment. Therefore, we found that it is preferable to use a conservative step length update scheme. The simple scheme (6) works well.

Although the initial layout in graph prolongated from the coarser graph is usually globally well positioned, a naive application of Algorithm 1 would cause large movement of vertices, thus potentially destroying the useful information inherited. For example, in the context of the spring model, the physical distance between two vertices and in the initial layout in is roughly the same as the graph distance of the corresponding vertices in , that is

where and are two vertices in the coarser graph that corresponds to and . However, to minimize the energy on level , we want to be as close to the graph distance of them in , that is, we want

Typically is much smaller than . If the initial layout is used as is, then to achieve the minimal energy, the graph has to be expanded by the ratio between these two distances through a serious of large moves, which is inefficient and could lose some information in the initial good layout.

Therefore, for a multilevel algorithm based on the spring model, we scale the initial coordinates by the ratio of the pseudo-diameters between the two subsequent levels of graphs,

For the spring-electrical model, Walshaw [2] suggested keeping the coordinates unchanged but reducing the natural spring length to

with . Walshaw derived this value based on examining a graph with four vertices. We use instead (10) and found it to be equally effective. On the coarsest level, we set to be the average edge length of the initial random layout, as in [2].

To avoid the complexity of the repulsive force calculation in the spring-electrical model, Walshaw [2], following Fruchterman and Reigold [4], cut off the contributions from faraway vertices. Only repulsive forces from vertices within a certain radius were considered. Specifically, on the th level, for vertex , repulsive forces from vertex were ignored when . If a small radius is chosen, then repulsive force over even a short distance is ignored. This can cause faraway regions to collapse into each other due to the lack of force to spread them out. On the other hand, a larger radius is expensive. In the extreme, gives us the complexity. Walshaw [2] proposed the radius

Notice that the radius is larger, relative to the natural spring length, on the coarser graphs, for which a large value would not be too costly due to the smaller sizes of the graphs. The effect of this cutoff, which would otherwise be more profound, was largely dampened because of the multilevel approach. Overall, the power of the multilevel approach means that the good quality global layout achieved on coarser graphs was inherited by the finer graphs, and a small radius on the finest graphs usually worked well. Nevertheless, we found that for some graphs, particularly those with a hollow interior, such as the graph finan512 in Section 6, the adverse effect of ignoring long-range repulsive force was obvious. With our use of octree data structure, we no longer need to use a cutoff radius for the spring-electrical model. Nevertheless we set a cutoff radius of

and by default we set , which is equivalent to not using a cutoff radius at all. This, however, also allows us to have a finite value to experiment with. For the spring model, to avoid calculation of the all-to-all distance matrix needed to compute the force (5), we used a similar strategy, by only calculating the distance of two vertices and and their attractive/repulsive forces, if

with a default value of 4.

5.4. The Multilevel Algorithm

We present the overall multilevel algorithm in the following. In the algorithm, is the number of vertices in the th level graph . is the coordinate vector for the vertices in . We represent by a symmetric matrix , with the entries of the matrix the edge weights. The prolongation operator from to is also represented by a matrix , of dimension . For details on the implementation of the multilevel process, and some examples, see [24]. The starting point is the original graph,

function MultilevelLayout

Algorithm 2. A multilevel force-directed algorithm.

In Algorithm 2, coarsening will stop if the graph is too small, , or there is not enough coarsening, . We used and .