Energy Models for Drawing Clustered Small-World Graphs

Andreas Noack
Software Systems Engineering Research Group
Department of Computer Science
Brandenburg Technical University at Cottbus
PO Box 10 13 44, 03013 Cottbus, Germany
an@informatik.tu-cottbus.de

Abstract.  We introduce energy models for drawing clustered small-world graphs.
Clustered means that there exist (probably unknown) sets of nodes with many
edges between nodes of the same set and few edges to nodes outside the set.
Small-world means that the graph-theoretic distances between nodes are small
relative to the number of nodes.  Previous force or energy models do not produce
satisfactory results for such graphs.  In drawings that have minimum energy with
respect to our new energy models, different clusters are clearly separated and
have interpretable distances.
We formally characterize the minimum energy drawings of our new energy models
and of a class of energy models that contains among others the well-known
Fruchterman-Reingold model.  These characterizations show 1) in what sense the
minimum energy drawings of these energy models fulfill requirements like small,
uniform edge lengths, well-distributed nodes, or separated clusters, and 2) what
properties of the drawn graph can be inferred from the drawings.