Classical Algorithms in Force-Directed Placement
Accumulated force models
Accumulated force models follow the simulation of a spring system, in which the length of the spring is proportional to the force exerted by an extended spring. Repulsive and attractive forces are basic forces defined in the accumulated force models. The repulsive force is computed for every node pair and the attractive force is computed for every adjacent node.
The sum of the values of repulsive and attractive forces for each node is stored in the temporary variables, which can be used for updating the nodes’ positions. Most accumulated force models follow Hooke’s law. Eades algorithm, Fruchterman–Reingold (FR) algorithm, and ForceAtlas2 (FA2) algorithm fall under this category.
Eades algorithm
The idea of Eades’ spring-embedded algorithm is to model a network as a magnetized system with rings representing nodes and the length of edges represented by the spring. Eades was the first algorithm to consider attractive and repulsive forces. The attractive force fₐ is applied to nodes that have a direct connection by an edge (i.e. d(i,j)=1d(i,j)=1), and the repulsive force fᵣ is applied to nodes that have an indirect connection (i.e. d(i,j)>1d(i,j)>1). The attractive and repulsive forces of the Eades algorithm are defined as follows:
where d(i,j)d(i,j) is the distance between node i and j, d₀ is the ideal edge length, and Cₐ and Cᵣ are the constants. The aim of the algorithm is to find zero-force locations for all nodes to reach a state of equilibrium for the spring system.
FR algorithm
The FR algorithm is based on the Eades algorithm. Like the Eades algorithm, the FR algorithm uses two forces, with the attractive force (fₐ) and repulsive force (fᵣ).
The FR algorithm is executed iteratively. In each iteration, all of the nodes are moved simultaneously after the forces have been calculated. When updating the position of the nodes, the algorithm adds a ‘displacement’ attribute to store the position offset of the nodes. At the start of each iteration, the initial values of the displacement for all of the nodes are calculated using the repulsion force (fᵣ). The algorithm uses the attraction force (fₐ)to iteratively update the position of the nodes on every edge. Finally, it updates the position offset of the nodes using the displacement value.
The displacement scale, s, is used as the termination condition of the FR algorithm. When the displacement scale, s, is lower than the threshold value, the algorithm is terminated. When the algorithm is initialized, the value of the displacement scale, s, is set to W/10. This value is updated in each iteration according to the iteration count and the maximum number of iterations set by the user.
FA2 algorithm
FA2 was proposed by Jacomy to satisfy speed and precision for network visualization. The algorithm extends the FR algorithm. Its authors proposed a revised attractive force based on the LinLog model and defined it as follows:
where d is the distance between nodes n1 and n2. Moreover, a degree-dependent repulsion model was proposed in the FA2 algorithm to reduce the repulsive forces. This repulsion model increases the chances of lower-than-average-degree nodes connecting to higher-than-average-degree nodes.
In addition, the FA2 algorithm also uses gravitational force and strong gravitational force. Jacomy concluded that strong gravitational force may be useful only for specific types of networks.
