An algorithm for minimizing the energy of the model usually works in the following way: It starts with an initial layout, where the positions of the vertices are randomly assigned. Then, in every iteration, the algorithm tries to improve the layout according to the energy model (by using the first derivation of the energy function to compute a direction and a distance for the movement of each vertex). Since the graphs we have to deal with are usually large (especially software graphs), we cannot afford to use algorithms with complexity in O(V^{2}) per iteration. The algorithm of Barnes and Hut [BH86] is in O(E + V logV) per iteration, and is therefore sufficient for our purposes.
The energy model encodes decisions about what is considered to be a good layout. In the following, we briefly introduce some of the energy models that are supported by CCVisu. First give the concrete models, and at the end we explain our generic model that can be instantiated for each of the concrete models.
We use the following notation: A graph G=(V, E) consists of a set of vertices V and a set of edges E ⊆ V^{(2)}, where V^{(2)} = {{u,v}  u,v∈ V} contains all sets with two vertices (i.e., undirected edges). A layout p: V → ℜ^{d} is a function that assigns to each vertex a position in the ddimensional space (d ∈ {2, 3} is the number of dimensions, ℜ is the set of real numbers), P is the set of all layouts. An energy model U: P → ℜ is a function that assigns to each layout a real number (the smaller the value the better the layout). For a given layout p and two vertices u and v, the term p(u) − p(v) denotes the Euclidean distance of the two vertices.
The energy model of Fruchterman and Reingold
was designed to enforce layouts with uniform edge length [FR91].
It requires graph with a large diameter (or graphtheoretic distance),
for which it produces esthetic graph layouts.
The energy for a layout p is defined as:

The first term of the sum is interpreted as attraction between connected vertices, because its value decreases when the distance of such vertices decreases. The second term is interpreted as repulsion between all pairs of (different) vertices, because its value decreases when the distance between any two vertices increases.
The vertexrepulsion LinLog energy model
was designed for visual graph clustering,
i.e., to produce layouts that fulfill certain clustering criteria [Noa04a].
It was the first energy model that was explicitly designed
for computing clustering layouts (of software graphs).
This model requires graphs with uniform edge degree to produce good layouts.
The energy for a layout p is defined as:

The edgerepulsion LinLog energy model is an extension of the
vertexrepulsion LinLog model to overcome the limitation to graphs of uniform edge degree.
It was successfully used in the initial study
of cochange visualization [BN05a].
Noack provides a detailed introduction and comparison
with the vertexrepulsion LinLog model in the technical report [Noa04b].
For a comparison with the FruchtermanReingold model we refer to
Section 7 (or to the technical report [BN05b]).
The energy for a layout p is defined as
(the edge degree of a vertex v is denoted by deg(v)):

In this energy model, the second term can be interpreted as repulsion between all pairs of edges (more precisely, between the end vertices of the edges).
The weighted edgerepulsion LinLog model is defined for graphs with weighted edges,
as a straight forward extension of the edgerepulsion LinLog model.
A weighted graph G=(V, E, w) consists of
a set of vertices V,
a set of edges E ⊆ V^{(2)}, and
a function w: E → ℜ, which assigns a real number (edge weight) to each edge.
(A graph is a weighted graph with w(e) = 1 for all edges e ∈ E.)
The weighted edge degree of a vertex v is
deg_{w}(v) = ∑_{{u, v} ∈ E} w({u, v}).
The energy for a layout p is defined as:

The tool CCVisu implements a generalization of the above mentioned energy models by using three parameters, which can be used to adjust the actual energy model by commandline options. (1) Option attrExp a applies value a as exponent to the distance in the attraction term. (2) Option repuExp r applies value r as exponent to the distance in the repulsion term if r ≠ 0, and applies the logarithm to the distance in the repulsion term if r = 0. (3) Option vertRepu eliminates the edgeweight factor in the repulsion term by setting e to value 0. The default values are a=1, r=0, and e=1, i.e., the default energy model is the weighted edgerepulsion energy model. Table 1 describes how to set the parameters for each abovementioned energy model.
For a weighted graph G=(V, E, w), the energy for a layout p is defined as:

with the attraction exponent a ∈ ℜ, the repulsion exponent r ∈ ℜ, and the edgerepulsion factor e ∈ {0, 1}.
Energy model attrExp a repuExp r vertRepu e Fruchterman Reingold 3 0 0 Vertexrepulsion LinLog 1 0 0 Edgerepulsion LinLog 1 0 1 Weighted edgerepulsion LinLog 1 0 1
The energy models for clustering software graphs —e.g., cochange graphs and call graphs— have to fulfill several clustering criteria, in particular, it should separate clusters and lead to interpretable distances. In difference to other graphdrawing applications, the energy models for software graphs must not enforce uniform edge length, must not be biased to the size of the clusters, and must be normalized to nonuniform degrees of the vertices. That is why we use the weighted edgerepulsion LinLog energy model (or its unweighted version) as the standard energy model. However, the generic energy model allows to express the many important energy models for software graphs in the current implementation, and the tool CCVisu is easy to extend to further variants and completely different energy models.
© Dirk Beyer