Force Directed Graphs

The methodology used to create this network graph’s layout is called “force-directed placement” (FDP). The basic idea is of two physical forces existing in the viewing area:

  1. the repulsive force of nodes on other nodes and
  2. the attractive force of links that bring nodes together.

The algorithm starts by placing nodes randomly across the viewing area and iterates until an equilibrium of these two forces is found, halting the algorithm.

Parameters

The two forces are parameters to the layout. I chose for the links to have a constant attraction, but gave the nodes a repulsion inversely proportional to the square of the node’s connectivity; this is why the highly connected nodes 1, 5 cluster towards each other in the center, while the least connected nodes 9, 4 are at the edges of the viewing area. This tends to give the layout a radial interpretation, where node connectivity is negatively correlated with radius from the center. This effect is, however, non-deterministic due to the random initial states inherent to FDPs and these parameters may not provide this effect to all datasets.

Node Size

I also encoded connectivity with node size: highly connected nodes have greater radii and vice versa. This additional encoding of connectivity reinforces its meaning, but also provides a fallback in case a particular FDP run produces a placement that contradicts my intentions from the previous paragraph.

Color

The colormap used for nodes was chosen with the assumption that nodes are not part of a continuity and are more categorical in nature. Therefore, the colors were intended to be discriminable. I used D3.js’s category10() color scale.

Motivation

While my first reaction to the data was to make a planar graph, I thought it more interesting and organic to use an FDP. Human adjustment to particular nodes and links can place undue emphasis on information. Although the randomness of FDPs may not be much better, at least it gives consistent treatment to the whole system.

Graph Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
var width = 600,
    height = 500;

var color = d3.scale.category10();

var radius = d3.scale.pow().range([15,30]).domain([2,4]);

var charge = d3.scale.pow().range([-100,-5000]).domain([2,4]);

var svg = d3.select("#svg").append("svg")
    .attr("width", width)
    .attr("height", height);

var dataPath = d3.select("#svg").attr("data-json-path");

d3.json(dataPath, function(error, graph) {

  var force = d3.layout.force()
      .size([width, height])
      .nodes(graph.nodes)
      .links(graph.links)
      .charge(function(d) { console.log(d);return charge(d.id.degree); } )
      .distance(40)
      .on("tick", tick)
      .start();

  var drag = force.drag()
      .on("dragstart", dragstart);

  var link = svg.selectAll(".link")
      .data(graph.links)
    .enter().append("line")
      .attr("class", "link")
      .style("stroke", "#444")
      .style("stroke-opacity", ".6")
      .style("stroke-width", "4");

  var nodeg = svg.selectAll(".node")
      .data(graph.nodes)
    .enter().append("g")
      .attr("class", "node")
      .on("dblclick", dblclick)
      .call(drag);

  var node = nodeg.append("circle")
      .attr("r", function(d) { return radius(d.id.degree); } )
      .style("fill", function(d,i) { return color(i); })
      .style("stroke", "#222")
      .style("stroke-width", "1.5px")

  nodeg.append("text")
      .style("font", "16px sans-serif")
      .style("fill", "#000")
      .attr("dx", "-0.25em")
      .attr("dy", "0.35em")
      .text(function(d) { return d.id.i; });

  function tick() {
    link.attr("x1", function(d) { return d.source.x; })
        .attr("y1", function(d) { return d.source.y; })
        .attr("x2", function(d) { return d.target.x; })
        .attr("y2", function(d) { return d.target.y; });

    // nodeg.attr("cx", function(d) { return d.x; })
        // .attr("cy", function(d) { return d.y; });
    nodeg.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; });
  }

  function dblclick(d) {
    d3.select(this).classed("fixed", d.fixed = false);
  }

  function dragstart(d) {
    d3.select(this).classed("fixed", d.fixed = true);
  }
});

Graph Data

1
{"graph": [], "directed": false, "multigraph": false, "links": [{"target": 2, "source": 0}, {"target": 5, "source": 0}, {"target": 6, "source": 0}, {"target": 8, "source": 1}, {"target": 2, "source": 1}, {"target": 5, "source": 1}, {"target": 7, "source": 1}, {"target": 9, "source": 2}, {"target": 8, "source": 3}, {"target": 4, "source": 3}, {"target": 6, "source": 3}, {"target": 7, "source": 4}, {"target": 8, "source": 5}, {"target": 9, "source": 5}, {"target": 7, "source": 6}], "nodes": [{"id": {"i": 0, "degree": 3}}, {"id": {"i": 1, "degree": 4}}, {"id": {"i": 2, "degree": 3}}, {"id": {"i": 3, "degree": 3}}, {"id": {"i": 4, "degree": 2}}, {"id": {"i": 5, "degree": 4}}, {"id": {"i": 6, "degree": 3}}, {"id": {"i": 7, "degree": 3}}, {"id": {"i": 8, "degree": 3}}, {"id": {"i": 9, "degree": 2}}]}