Force-Directed Graphs: Drawing a Network by Simulating Physics

Turning a graph into a physics problem

A graph -- nodes and the edges connecting them -- has no inherent 2-D layout; the same graph can be drawn a hundred different ways, most of them an unreadable tangle. Force-directed layout sidesteps the combinatorics of finding a good drawing by turning the problem into a physics simulation: treat every node as a charged particle that repels every other node, and every edge as a spring that pulls its two connected nodes together. Run the simulation forward and let it settle to a low-energy configuration, and the resulting layout tends to be readable almost by accident -- connected nodes end up close together, unconnected nodes spread apart, and symmetric substructures in the graph often produce visually symmetric layouts, all without the algorithm ever being told anything about aesthetics.

Fruchterman-Reingold: the standard formulation

The most widely used version, due to Fruchterman and Reingold (1991), defines two forces from a single characteristic distance k (roughly the ideal edge length, often set from the layout area divided by the number of nodes):

repulsive force (every node pair):   Fr(d) = k^2 / d
attractive force (edge pairs only):  Fa(d) = d^2 / k

d = distance between the two nodes

Repulsion pushes every pair of nodes apart with a force that grows as they get closer (d in the denominator), preventing nodes from ever collapsing on top of each other; attraction pulls connected nodes together with a force that grows the farther apart they are (d in the numerator), like a spring being stretched. At the characteristic distance k the two forces roughly balance, which is why k acts as a target edge length: increase it and the whole layout spreads out, decrease it and nodes pack tighter.

Why it needs cooling, and why it's expensive

Left to iterate at full force forever, nodes can oscillate around their equilibrium instead of settling, bouncing back and forth as the two forces overcorrect each other. The standard fix is simulated annealing: limit how far a node can move in a single step (a "temperature" cap), and shrink that cap gradually over the run so early iterations make large, coarse rearrangements and later iterations make small, precise adjustments -- exactly the same cooling-schedule idea used in simulated-annealing optimisation generally. Computationally, repulsion between every pair of nodes costs O(n^2) per iteration, which is fine for graphs of a few hundred nodes but becomes the bottleneck for thousands; production layout engines use a Barnes-Hut-style spatial approximation (the same quadtree trick used for N-body gravity simulations) to group distant clusters of nodes into a single approximate repulsion source, cutting the cost to roughly O(n log n).

Random graph models feed the same layout differently

The visual character of a force-directed layout says as much about the graph structure as about the algorithm. An Erdos-Renyi random graph (each possible edge included independently with fixed probability p) tends to lay out as a fairly uniform, undifferentiated blob, since it has no preferential structure to cluster around. A Barabasi-Albert graph, built by preferential attachment where new nodes are more likely to connect to already-popular nodes, produces a small number of high-degree hub nodes -- and those hubs visibly pull large numbers of low-degree nodes into orbit around them under the spring forces, since a hub with many edges experiences many attractive pulls converging on it. A Watts-Strogatz small-world graph -- a ring lattice with a few edges randomly rewired -- lays out as a locally clustered ring with occasional long-range shortcut edges cutting visibly across the layout, a direct visual signature of the "small-world" property (short average path length despite high local clustering) that the model is built to produce.

Reading a settled layout

Once the simulation has cooled, several structural properties become visually legible for free. Densely interconnected communities pull each other into tight, visually distinct clusters (because internal edges pull constantly while there is comparatively little pulling them toward other clusters). Bridge nodes and bridge edges connecting two clusters get visibly stretched, since they are fighting the pull of two separate clusters at once. Node degree correlates loosely with centrality of position, because a highly connected node is pulled toward many others simultaneously and tends to be dragged toward the layout's centre of mass. None of this is programmed explicitly -- it is a side effect of minimising the same energy function that placed every node in the first place.

Frequently asked questions

Try it live

Everything above runs in your browser — open Force-Directed Graph and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.