All examples By author By category About

rpgove

Linear-time force-directed graph layouts with random vertex sampling

A simple example showing how to use d3.forceManyBodySampled() from d3-force-sampled for force-directed graph layouts. This example shows the dwt_1005 benchmark graph, which has 1005 vertices and 4813 edges.

d3.forceManyBodySampled() is a fast force calculation replacement for d3.forceManyBody(). It achieves this performance improvement by using Random Vertex Sampling instead of the Barnes-Hut approximation. Instead of computing Coulombic forces on every vertex at every iteration, Random Vertex Sampling only computes forces on a subset of vertices. And for each vertex in that subset, Random Vertex Sampling uses a different random sample of vertices to compute forces. This results in an algorithm that runs in linear time with linear space requirements. See d3-force-sampled and the research paper for more details:

Robert Gove. "A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts." Computer Graphics Forum 38, 3 (2019). Preprint PDF.