D3 Examples - Consensus Dynamics II

Consensus Dynamics II

Simulates consensus dynamics based off of a provided graph-Laplacian matrix. For each simulation random points are generated in (x,y) coordinates from the range [-50,50] and are updated with each time step as they propogate towards convergence. That convergence is directly impacted by the structure of the corresponding graph that is being modeled.

With each graph the eigenvalues are also listed, where the Fiedler eigenvalue is the first non-zero eigenvalue. You can see the dynamics where with lower Fiedler eigenvalues the graph takes longer to converge.

Instructions

Use the Select Graph dropdown to choose which graph to model.

Click the Reset button to generate new points for the same graph structure.

Feedback can be played live by using the Play and Pause buttons. When playing, the points will update for each iteration until they reach relative convergence (where the change is close to zero between iterations).

Iterations can also be forwarded manually by pressing the Next button.

Note: The x axis and y axis are not currently on the same scale.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style> /* set the CSS */
  .point {
    fill: black;
  }
​
  .t_old {
    fill: darkgrey
  }
  
.toolTip {
  pointer-events: none;
    position: absolute;
  display: none;
  width: 130px;
  height: auto;
  background: none repeat scroll 0 0 #ffffff;
  padding: 9px 14px 6px 14px;
  border-radius: 2px;
  text-align: center;
  line-height: 1.3;
  color: #5B6770;
  box-shadow: 0px 3px 9px rgba(0, 0, 0, .15);
}
.toolTip:after {
  content: "";
  width: 0;
  height: 0;
  border-left: 12px solid transparent;
  border-right: 12px solid transparent;
  border-top: 12px solid white;
  position: absolute;
  bottom: -10px;
  left: 50%;
  margin-left: -12px;
}  
.toolTip span {
    font-weight: 500;
  color: #081F2C;
}
  
  li a {
    cursor: pointer;
  }
</style>
<body>
<!-- load the d3.js library and other dependencies -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://www.numericjs.com/lib/numeric-1.2.6.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script>
​
  <div class="container-fluid">
    <div class="row">
      <div class="col-sm-9" id="svg-bin"></div>
      <div class="col-sm-3">
        <b>Converged:</b> <span id="is-converged">False</span>
        <br>
        <b>Iterations:</b> <span id="iters">0</span>
        <br>
        
        <div class="dropdown">
          <button class="btn btn-primary dropdown-toggle" type="button" data-toggle="dropdown">Select Graph
          <span class="caret"></span></button>
          <ul class="dropdown-menu">
            <li><a onclick="selectGraph('two-nodes')">Two Nodes</a></li>
            <li><a onclick="selectGraph('three-line')">Line</a></li>
            <li><a onclick="selectGraph('four-full')">Fully Connected</a></li>
            <li><a onclick="selectGraph('five-ring')">Ring</a></li>
            <li><a onclick="selectGraph('eight-disconnected')">Two Components</a></li>
            <li><a onclick="selectGraph('three-full')">Triangle</a></li>
            <li><a onclick="selectGraph('five-x')">X Graph</a></li>
            <li><a onclick="random_graph(10, 0.5)">Ten Random</a></li>
          </ul>
      </div>
      <br>
      <b>Eigenvalues:</b> <span id="eigs"></span>
      </div>
    </div>
    <div class="row">
      <button class="btn btn-danger" onclick="reset()">Reset</button>
      <button onclick="start()"><span class="glyphicon glyphicon-play"></span></button>
      <button onclick="stop()"><span class="glyphicon glyphicon-pause"></span></button>
      <button onclick="next()"><span class="glyphicon glyphicon-step-forward"></span></button>
    </div>
  </div>
  
<!-- Script to Run -->
<script>
// === Setup SVG ===
// set the dimensions and margins of the graph
var margin = {top: 20, right: 20, bottom: 30, left: 50},
    width = 720 - margin.left - margin.right,
    height = 450 - margin.top - margin.bottom;
​
// set the ranges
var x = d3.scaleLinear().range([0, width]);
var y = d3.scaleLinear().range([height, 0]);
​
// append the svg obgect to the body of the page
// appends a 'group' element to 'svg'
// moves the 'group' element to the top left margin
var svg = d3.select("#svg-bin").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform",
          "translate(" + margin.left + "," + margin.top + ")");
​
​
  
// === Tooltip display functions ===
var tooltip = d3.select("body").append("div").attr("class", "toolTip");
var mouseover = (d) => {
  tooltip.style("opacity", 1.0)
        .style("left", x(d.x) - 15 + "px")
        .style("top", y(d.y) - 25 + "px")
        .style("display", "inline-block")
        .html("(" + d.x.toFixed(3) + ", " + d.y.toFixed(3) + ")" )
}
var mouseout = (d) => {
  tooltip.style("opacity", 0.0);
}
​
​
​
​
// === Consensus Dynamics Variables ===
// change rate
var dt = 0.09;
​
// Global Variables
var timer;
var iters = 0;
​
// Graph Laplacians
var GRAPHS = {
  'two-nodes': [[1, -1],
                [-1, 1]],
  'three-line': [[ 1,-1, 0],
                         [-1, 2,-1],
                         [ 0,-1, 1]],
  'four-full': [[ 3,-1,-1,-1],
                [-1, 3,-1,-1],
                [-1,-1, 3,-1],
                [-1,-1,-1, 3]],
  'five-ring': [[ 2,-1, 0, 0,-1],
                [-1, 2,-1, 0, 0],
                [ 0,-1, 2,-1, 0],
                [ 0, 0,-1, 2,-1],
                [-1, 0, 0,-1, 2]],
  'eight-disconnected': [[ 2,-1,-1, 0, 0, 0, 0, 0],
                                             [-1, 2,-1, 0, 0, 0, 0, 0],
                                         [-1,-1, 2, 0, 0, 0, 0, 0],
                         [ 0, 0, 0, 1, 0,-1, 0, 0],
                         [ 0, 0, 0, 0, 1,-1, 0, 0],
                         [ 0, 0, 0,-1,-1, 4,-1,-1],
                         [ 0, 0, 0, 0, 0,-1, 1, 0],
                         [ 0, 0, 0, 0, 0,-1, 0, 1]],
  'five-x':    [[ 1, 0,-1, 0, 0],
                [ 0, 1,-1, 0, 0],
                [-1,-1, 4,-1,-1],
                [ 0, 0,-1, 1, 0],
                [ 0, 0,-1, 0, 1]],
  'three-full': [[ 2,-1,-1],
                         [-1, 2,-1],
                         [-1,-1, 2]]
}
​
​
​
// current graph
var L = GRAPHS['three-line'];
​
  
  
// === Consensus Dynamics Functions ===
// random point generator
var generate_random = function(num_agents) {
  var dataset = []
  for (var i = 0; i < num_agents; i++) {
    var x = d3.randomUniform(-50,50)();
    var y = d3.randomUniform(-50,50)();
    dataset.push({"x": x, "y": y});
  }
  return dataset
}
// gets next position
var update_position = function(Xt) {
  // convert to vector format
  var xt = Xt.map((n) => n["x"]);
  var yt = Xt.map((n) => n["y"]);
  
  // get derivaive
  var x_dot = numeric.dot(L, xt);
  var y_dot = numeric.dot(L, yt);
  
  // IMPORTANT: scale results by dt!
  x_dot = numeric.mul(x_dot, dt);
  y_dot = numeric.mul(y_dot, dt);
  
  // new point position
  var x_new = numeric.sub(xt, x_dot);
  var y_new = numeric.sub(yt, y_dot);
  
  // format result
  var result = [];
  for(var i = 0; i < Xt.length; i++) {
    result[i] = {"x": x_new[i], "y":y_new[i]}
  }
  return [result, x_dot, y_dot];
}
​
​
​
// === Drawing Stuff ===
var initialize = function() {
  // scale the range of the data
  x.domain([-50, 50]);
  y.domain([-50, 50]);
  
  // add the X Axis
  svg.append("g")
    .attr("transform", "translate(0," + height + ")")
    .call(d3.axisBottom(x));
​
  // add the Y Axis
  svg.append("g")
    .call(d3.axisLeft(y));
}
​
var draw_points = function(data) {
  svg.selectAll()
    .data(data)
    .enter().append("circle")
    .attr("r", 5)
    .attr("class", "point t_current")
    .attr("cx", function(d) { return x(d.x); })
    .attr("cy", function(d) { return y(d.y); })
    .on("mouseover", mouseover)
        .on("mouseout", mouseout)
}
// clears board and draws new random points
var reset = function() {
  // clear previous points
  svg.selectAll(".point").remove();
  
  // reset timer
  if (timer) {
    timer.stop();
  }
  
  // not converged
  d3.select("#is-converged").text("False");
  iters = 0;
  d3.select("#iters").text(0);
  
  // display eigenvalues
  var eigs = eigenvalues();
  d3.select("#eigs").text(eigs.join(', '));
  
  
  // generate one point for each agent
  var data = generate_random(L.length);
  
  // format the data
  data.forEach((d) => {
    d.x = +d.x;
    d.y = +d.y;
  });
  
  // draw points
  draw_points(data);
}
​
// draws next iteration of convergence
var next = function() {
    old_points = svg.selectAll(".t_current");
  
  // fade old points
    old_points
    .attr("class", "point t_old")
    .attr("r", 4)
    .on("mouseover", null);
  
  // draw new points
  var [new_points, dx, dy] = update_position(old_points.data());
  draw_points(new_points);
  var converged_x = dx.map((x) => x.toFixed(2) == 0.0).every(t => t);
  var converged_y = dy.map((y) => y.toFixed(2) == 0.0).every(t => t);
  
  // check if converged
  var conv = converged(dx, dy);
  if (conv) {
    d3.select("#is-converged").text("True");
  }
  
  //update iteration count
  iters++;
  d3.select("#iters").text(iters);
  
  return conv;
}
​
var converged = function(dx, dy) {
  var cx = dx.map((x) => x.toFixed(1) == 0.0).every(t => t);
  var cy = dy.map((y) => y.toFixed(1) == 0.0).every(t => t);
  return cx && cy
}
​
var start = function() {
  timer = d3.interval(() => {
    var conv = next();
    if (conv) {
      timer.stop();
      console.log("stopped!");
    }
  }, 200);
}
​
var stop = function() {
  timer.stop();
}
​
var selectGraph = function(g) {
  L = GRAPHS[g];
  console.log("L", g, L);
  reset();
}
​
var random_graph = function(size, p) {
  // create (size x size)empty matrix
  var Q = [];
  for (var i = 0; i < size; i++) {
    Q[i] = new Array(10);
    Q[i].fill(0);
  }
  
  // randomly connect nodes and create Laplacian
  for(var i = 0; i < size; i++) {
    for(var j = 0; j < size; j++) {
      if (i === j) { break; }
      var rand = Math.random();
      if (rand < p) {
        // Adjacency
        Q[i][j] = -1.0;
        Q[j][i] = -1.0;
        // Degree
        Q[i][i] += 1;
        Q[j][j] += 1;
      }
    }
  }
  
  L = Q;
  console.log("L 10-random", p);
  console.info(L.join('\n'))
  reset();
}
​
var eigenvalues = function() {
  var result = numeric.eig(L);
  return result['lambda'].x.map((x) => +x.toFixed(3)).sort();
}
​
// === Run This on page-load ===
initialize();
reset();
​
</script>
  
</body>
​
    