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.

forked from lwthatcher's block: Consensus Dynamics Diffusion

<!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>

<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>
// === 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));
}

// 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 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>

Modified http://www.numericjs.com/lib/numeric-1.2.6.js to a secure url

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

https://www.numericjs.com/lib/numeric-1.2.6.js

https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js

https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js