Random Vertex Sampling vs. Barnes-Hut Approximation

A performance comparison of d3.forceManyBodySampled() in d3-force-sampled and the standard d3.forceManyBody() in d3-force. d3.forceManyBodySampled() tends to perform 2-3x faster than d3.forceManyBody() on common graph sizes. It achieves this performance improvement by using the Random Vertex Sampling algorithm instead of the Barnes-Hut approximation, and therefore it achieves linear runtime and space complexity. 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.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  body {
    font-family: Arial, "Helvetica Neue", Helvetica, sans-serif;
    background: white;
  }

.container {
    width: 840px;
  }

canvas {
    display: inline-block;
    margin: 10px;
  }

svg {
    display: block;
    margin: auto;
  }

text {
    font-size: 12px;
    fill: #333;
  }

.axis text {
    font-weight: normal;
  }

.sampled {
    fill: #d30000;
  }

.bh {
    fill: #666;
  }
</style>
<body>

var radius = 1;
var margin = {left: 150, right: 20, top: 0, bottom: 35};

d3.json('tvcg.json').then(function(graph) {
  graph.links.forEach(function (l) {
    l.source = graph.nodes[l.source];
    l.target = graph.nodes[l.target];
  })

drawNetwork(graph, 'sampled', document.querySelector('#sampled'));
  drawNetwork(graph, 'bh', document.querySelector('#bh'));

var timeData = ['sampled', 'bh'].map(function (d) {
    var mean = d3.mean(graph.time[d]);
    return { name: d, mean: mean };
  });

var svg = d3.select('svg');
  var width = +svg.attr('width') - margin.left - margin.right;
  var height = +svg.attr('height') - margin.top - margin.bottom;

var xScale = d3.scaleLinear()
    .domain([0, d3.max(timeData, function (d) { return d.mean; })])
    .range([0, width])
    .nice();

var yScale = d3.scaleBand()
    .domain(timeData.map(function (d) { return d.name; }).reverse())
    .range([height, 0])
    .padding(0.4);

svg = svg.append('g')
    .attr('transform', 'translate(' + margin.left + ',' + margin.top + ')');

svg.selectAll('rect').data(timeData)
    .enter().append('rect')
    .attr('class', function (d) { return d.name; })
    .attr('width', function (d) { return xScale(d.mean); })
    .attr('height', function (d) { return yScale.bandwidth(); })
    .attr('x', 0)
    .attr('y', function (d) { return yScale(d.name); });

svg.append('g')
    .attr('transform', 'translate(0,' + height + ')')
    .call(d3.axisBottom(xScale))
    .append("text")
    .attr("fill", "#000")
    .attr('transform', 'translate(0,0)')
    .attr("y", 21)
    .attr("dy", "0.71em")
    .attr("text-anchor", "start")
    .text("Mean runtime (seconds)");

svg.append('g')
    .attr('transform', 'translate(0,' + 0 + ')')
    .call(d3.axisLeft(yScale).tickSizeOuter(0).tickFormat(function (d) {
      return displayName(d);
    }));
});

function drawNetwork (graph, simType, canvas) {
  var context = canvas.getContext('2d');
  var width = canvas.width;
  var height = canvas.height;

var xScale = d3.scaleLinear()
    .range([radius, width - radius]);
  var yScale = d3.scaleLinear()
    .range([radius, height - radius]);

// Adjust scales
  xScale.domain([
    d3.min(graph.nodes, function (d) { return Math.min(d[simType].x, d[simType].y); }),
    d3.max(graph.nodes, function (d) { return Math.max(d[simType].x, d[simType].y); })
  ]);
  yScale.domain([
    d3.min(graph.nodes, function (d) { return Math.min(d[simType].x, d[simType].y); }),
    d3.max(graph.nodes, function (d) { return Math.max(d[simType].x, d[simType].y); })
  ]);

context.clearRect(0, 0, width, height);
  context.fillStyle = '#ffffff';
  context.fillRect(0, 0, width, height);

context.font = '12px Arial';
  context.fillStyle = '#333';
  context.fillText(displayName(simType), 10, 10);

// Draw links.
  context.strokeStyle = 'rgba(90, 90, 90, 0.30)';
  context.lineWidth = 1;
  graph.links.forEach(function(d) {
    context.beginPath();
    var pos = [xScale(d.source[simType].x), yScale(d.source[simType].y)];
    context.moveTo(pos[0], pos[1]);
    pos = [xScale(d.target[simType].x), yScale(d.target[simType].y)];
    context.lineTo(pos[0], pos[1]);
    context.stroke();
  });

// Draw nodes.
  context.fillStyle = '#d30000';
  if (simType === 'bh')
    context.fillStyle = '#333';
  context.beginPath();
  graph.nodes.forEach(function(d) {
    var pos = [xScale(d[simType].x), yScale(d[simType].y)];
    context.moveTo(pos[0], pos[1]);
    context.arc(pos[0], pos[1], radius, 0, 2 * Math.PI);
  });
  context.fill();
}

function displayName (dataName) {
  return dataName === 'bh' ? 'Barnes-Hut' : 'Random Vertex Sampling';
}

</script>

https://d3js.org/d3.v5.min.js