Force Approximation Reuse

I ran several experiments to test speeding up force-directed layout algorithms by reusing force approximations. Force-directed layout algorithms run iteratively, and commonly they use a Coulombic force approximation, such as Barnes-Hut, to run faster. However, vertex positions tend to change slowly, so it’s probable that reusing approximations might speed up layout algorithms at the cost layout quality. I tested this hypothesis using both Barnes-Hut and fast multiple approximation methods. I found that reusing the approximation and calculating a new one every 13 iterations reduces runtime by 9% to 18% without decreasing layout quality when using the Barnes-Hut approximation. This led me to develop the d3-force-reuse speed comparison module for D3.js. I published a research paper that discusses the experiments in more detail.

Live examples

• d3-force-reuse speed comparison
• Faster Force-Directed Graphs with d3-force-reuse

Blogs

Faster force-directed graph layouts by reusing force approximations

Code

• d3-force-reuse GitHub repo
• Open date for the experiments and analysis

Papers

Robert Gove. “It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts.” Forum Media Technology 2018, best paper award. [pdf] [osf]