Force-based Algorithms (graph Drawing)

Force-based Algorithms (graph Drawing)

Force-based or force-directed algorithms are a class of algorithms for drawing graphs in an aesthetically pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible. The idea originated in the 1980s with a spring-embedder model of Eades and Kamada-Kawai; the term force-directed comes from Fruchterman & Reingold's 1990 University of Illinois technical report (UIUCDCS-R-90-1609).

The force-directed algorithms achieve this by assigning forces among the set of edges and the set of nodes; the most straightforward method is to assign forces as if the edges were springs (see Hooke's law) and the nodes were electrically charged particles (see Coulomb's law). The entire graph is then simulated as if it were a physical system. The forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to an equilibrium state; i.e., their relative positions do not change anymore from one iteration to the next. At that moment, the graph is drawn. The physical interpretation of this equilibrium state is that all the forces are in mechanical equilibrium.

An alternative model considers a spring-like force for every pair of nodes where the ideal length of each spring is proportional to the graph-theoretic distance between nodes i and j. In this model, there is no need for a separate repulsive force. Note that minimizing the difference (usually the squared difference) between euclidean and ideal distances between nodes is then equivalent to a metric multidimensional scaling problem. Stress majorization gives a very well-behaved (i.e., monotonically convergent) and mathematically elegant way to minimise these differences and, hence, find a good layout for the graph.

A force-directed graph can involve forces other than mechanical springs and electrical repulsion; examples include logarithmic springs (as opposed to linear springs), gravitational forces (which aggregate connected components in graphs that are not singly connected), magnetic fields (so as to obtain good layouts for directed graphs), and electrically charged springs (in order to avoid overlap or near-overlap in the final drawing). In the case of spring-and-charged-particle graphs, the edges tend to have uniform length (because of the spring forces), and nodes that are not connected by an edge tend to be drawn further apart (because of the electrical repulsion).

While graph drawing is a difficult problem, force-directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as planarity.

It is also possible to employ mechanisms that search more directly for energy minima, either instead of or in conjunction with physical simulation. Such mechanisms, which are examples of general global optimization methods, include simulated annealing and genetic algorithms.