Node-link polar layout with centrality (eigenvector)

README.md

A variation on the previous experiment. This time, eigenvector centrality is used to control the distance of the nodes from the origin (the closer to the origin, the more central the node). Please note that, even if depicted, the weight of links is not considered when computing a node's centality.

The result seems not so informative, but it should be tested with a greater number of nodes.

The following R script, adapted from this post, was used to compute the centrality measure:

library(network)

src <- c("A", "A", "A", "A", "A", "B", "B", "B", "B", "C", "C", "D", "D", "E")
dst <- c("B", "C", "D", "F", "G", "D", "E", "F", "G", "D", "E", "E", "F", "F")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist", directed=FALSE)

EV <- eigen(as.matrix(Net))
centrality <- data.frame(EV$vectors[,1]) 
centrality = abs(centrality)
names(centrality) <- "Centrality"

print(centrality)

index.coffee

# data
graph_data = {
  nodes: [
    {id: 'A', centrality: {degree: 5, eigenvector: 0.4214039}},
    {id: 'B', centrality: {degree: 5, eigenvector: 0.4364557}},
    {id: 'C', centrality: {degree: 3, eigenvector: 0.2947939}},
    {id: 'D', centrality: {degree: 5, eigenvector: 0.4540865}},
    {id: 'E', centrality: {degree: 4, eigenvector: 0.3736236}},
    {id: 'F', centrality: {degree: 4, eigenvector: 0.3977985}},
    {id: 'G', centrality: {degree: 2, eigenvector: 0.2024569}}
  ],
  links: [
    {source: 'A', target: 'B', weight: 12},
    {source: 'A', target: 'C', weight:  2},
    {source: 'A', target: 'D', weight: 33},
    {source: 'A', target: 'F', weight:  5},
    {source: 'A', target: 'G', weight: 24},
    {source: 'B', target: 'D', weight: 10},
    {source: 'B', target: 'E', weight: 10},
    {source: 'B', target: 'F', weight:  8},
    {source: 'B', target: 'G', weight: 16},
    {source: 'C', target: 'D', weight: 29},
    {source: 'C', target: 'E', weight: 11},
    {source: 'D', target: 'E', weight:  4},
    {source: 'D', target: 'F', weight: 12},
    {source: 'E', target: 'F', weight: 19}
  ]
}

# objectify the graph
# resolve node IDs (not optimized at all!)
graph_data.links.forEach (l) ->
  graph_data.nodes.forEach (n) ->
    if l.source is n.id
      l.source = n
    
    if l.target is n.id
      l.target = n

svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

# translate the viewBox to have (0,0) at the center of the vis
svg
  .attr
    viewBox: "#{-width/2} #{-height/2} #{width} #{height}"
    
    
# layout
polar_layout = () ->
  rho = (d, i, data) -> 100
  theta_0 = (d, i, data) -> -Math.PI/2 # start from the angle pointing north
  delta_theta = (d, i, data) -> 2*Math.PI/data.length
  theta = (d, i , data) -> theta_0(d, i, data) + i*delta_theta(d, i, data)
  
  self = (data) ->
    data.forEach (d, i) ->
      d.rho = rho(d, i, data)
      d.theta = theta(d, i, data)
      d.x = d.rho * Math.cos(d.theta)
      d.y = d.rho * Math.sin(d.theta)
      
    return data
    
  self.rho = (x) ->
    if x?
      if typeof(x) is 'function'
        rho = x
      else
        rho = () -> x
        
      return self
    
    # else
    return rho
    
  self.theta_0 = (x) ->
    if x?
      if typeof(x) is 'function'
        theta_0 = x
      else
        theta_0 = () -> x
      
      return self
    
    # else
    return theta_0
  
  self.delta_theta = (x) ->
    if x?
      if typeof(x) is 'function'
        delta_theta = x
      else
        delta_theta = () -> x
      
      return self
    
    # else
    return delta_theta
  
  self.theta = (x) ->
    if x?
      if typeof(x) is 'function'
        theta = x
      else
        theta = () -> x
      
      return self
    
    # else
    return theta
  
  return self

# encode the eigenvector centrality as distance from the origin
distance = d3.scale.linear()
  .domain([0.1, 0.5])
  .range([460, 0])

# apply the layout
polar = polar_layout()
  .rho((node) -> distance(node.centrality.eigenvector))
  
polar(graph_data.nodes)

DIAMETER = 40

# draw the circular axes
svg.append('circle')
  .attr
    r: distance(0.1)
    fill: 'none'
    stroke: '#BDF'
    
svg.append('circle')
  .attr
    r: distance(0.2)
    fill: 'none'
    stroke: '#BDF'
    
svg.append('circle')
  .attr
    r: distance(0.3)
    fill: 'none'
    stroke: '#BDF'

svg.append('circle')
  .attr
    r: distance(0.4)
    fill: 'none'
    stroke: '#BDF'
    
svg.append('circle')
  .attr
    r: 4
    fill: '#BDF'
    
# draw nodes above links
links_layer = svg.append('g')
nodes_layer = svg.append('g')

nodes = nodes_layer.selectAll('.node')
  .data(graph_data.nodes)
  
nodes.enter().append('circle')
  .attr
    class: 'node'
    r: DIAMETER/2
    cx: (node) -> node.x
    cy: (node) -> node.y
    
# draw node labels
labels = nodes_layer.selectAll('.label')
  .data(graph_data.nodes)
  
labels.enter().append('text')
  .text((node) -> node.id)
  .attr
    class: 'label'
    dy: '0.35em'
    x: (node) -> node.x
    y: (node) -> node.y
    
link_thickness = d3.scale.linear()
  .domain([0, d3.max(graph_data.links, (link) -> link.weight)])
  .range([0, DIAMETER*0.8]) # links are never larger than the 80% of a node's diameter

links = links_layer.selectAll('.link')
  .data(graph_data.links)
  
links.enter().append('path')
  .attr
    class: 'link'
    d: (link) -> "M#{link.source.x} #{link.source.y} L#{link.target.x} #{link.target.y}"
    'stroke-width': (link) -> link_thickness(link.weight)
    

index.css

svg {
  background: white;
}

.node {
  fill: lightgray;
  stroke: gray;
  stroke-width: 2px;
}
.link {
  stroke: black;
  opacity: 0.1;
}
.label {
  text-anchor: middle;
  font-size: 16px;
  fill: #444;
  font-weight: bold;
  font-family: sans-serif;
}

index.html

<!DOCTYPE html>
<html>
	<head>
        <meta charset="utf-8">
        <meta name="description" content="Node-link polar layout with centrality" />
        <title>Node-link polar layout with centrality</title>
		<link type="text/css" href="index.css" rel="stylesheet"/>
        <script src="http://d3js.org/d3.v3.min.js"></script>
	</head>
	<body>
        <svg height="500" width="960"></svg>
        <script src="index.js"></script>
	</body>
</html>

index.js

(function() {
  var DIAMETER, distance, graph_data, height, labels, link_thickness, links, links_layer, nodes, nodes_layer, polar, polar_layout, svg, width;

  graph_data = {
    nodes: [
      {
        id: 'A',
        centrality: {
          degree: 5,
          eigenvector: 0.4214039
        }
      }, {
        id: 'B',
        centrality: {
          degree: 5,
          eigenvector: 0.4364557
        }
      }, {
        id: 'C',
        centrality: {
          degree: 3,
          eigenvector: 0.2947939
        }
      }, {
        id: 'D',
        centrality: {
          degree: 5,
          eigenvector: 0.4540865
        }
      }, {
        id: 'E',
        centrality: {
          degree: 4,
          eigenvector: 0.3736236
        }
      }, {
        id: 'F',
        centrality: {
          degree: 4,
          eigenvector: 0.3977985
        }
      }, {
        id: 'G',
        centrality: {
          degree: 2,
          eigenvector: 0.2024569
        }
      }
    ],
    links: [
      {
        source: 'A',
        target: 'B',
        weight: 12
      }, {
        source: 'A',
        target: 'C',
        weight: 2
      }, {
        source: 'A',
        target: 'D',
        weight: 33
      }, {
        source: 'A',
        target: 'F',
        weight: 5
      }, {
        source: 'A',
        target: 'G',
        weight: 24
      }, {
        source: 'B',
        target: 'D',
        weight: 10
      }, {
        source: 'B',
        target: 'E',
        weight: 10
      }, {
        source: 'B',
        target: 'F',
        weight: 8
      }, {
        source: 'B',
        target: 'G',
        weight: 16
      }, {
        source: 'C',
        target: 'D',
        weight: 29
      }, {
        source: 'C',
        target: 'E',
        weight: 11
      }, {
        source: 'D',
        target: 'E',
        weight: 4
      }, {
        source: 'D',
        target: 'F',
        weight: 12
      }, {
        source: 'E',
        target: 'F',
        weight: 19
      }
    ]
  };

  graph_data.links.forEach(function(l) {
    return graph_data.nodes.forEach(function(n) {
      if (l.source === n.id) {
        l.source = n;
      }
      if (l.target === n.id) {
        return l.target = n;
      }
    });
  });

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  svg.attr({
    viewBox: "" + (-width / 2) + " " + (-height / 2) + " " + width + " " + height
  });

  polar_layout = function() {
    var delta_theta, rho, self, theta, theta_0;

    rho = function(d, i, data) {
      return 100;
    };
    theta_0 = function(d, i, data) {
      return -Math.PI / 2;
    };
    delta_theta = function(d, i, data) {
      return 2 * Math.PI / data.length;
    };
    theta = function(d, i, data) {
      return theta_0(d, i, data) + i * delta_theta(d, i, data);
    };
    self = function(data) {
      data.forEach(function(d, i) {
        d.rho = rho(d, i, data);
        d.theta = theta(d, i, data);
        d.x = d.rho * Math.cos(d.theta);
        return d.y = d.rho * Math.sin(d.theta);
      });
      return data;
    };
    self.rho = function(x) {
      if (x != null) {
        if (typeof x === 'function') {
          rho = x;
        } else {
          rho = function() {
            return x;
          };
        }
        return self;
      }
      return rho;
    };
    self.theta_0 = function(x) {
      if (x != null) {
        if (typeof x === 'function') {
          theta_0 = x;
        } else {
          theta_0 = function() {
            return x;
          };
        }
        return self;
      }
      return theta_0;
    };
    self.delta_theta = function(x) {
      if (x != null) {
        if (typeof x === 'function') {
          delta_theta = x;
        } else {
          delta_theta = function() {
            return x;
          };
        }
        return self;
      }
      return delta_theta;
    };
    self.theta = function(x) {
      if (x != null) {
        if (typeof x === 'function') {
          theta = x;
        } else {
          theta = function() {
            return x;
          };
        }
        return self;
      }
      return theta;
    };
    return self;
  };

  distance = d3.scale.linear().domain([0.1, 0.5]).range([460, 0]);

  polar = polar_layout().rho(function(node) {
    return distance(node.centrality.eigenvector);
  });

  polar(graph_data.nodes);

  DIAMETER = 40;

  svg.append('circle').attr({
    r: distance(0.1),
    fill: 'none',
    stroke: '#BDF'
  });

  svg.append('circle').attr({
    r: distance(0.2),
    fill: 'none',
    stroke: '#BDF'
  });

  svg.append('circle').attr({
    r: distance(0.3),
    fill: 'none',
    stroke: '#BDF'
  });

  svg.append('circle').attr({
    r: distance(0.4),
    fill: 'none',
    stroke: '#BDF'
  });

  svg.append('circle').attr({
    r: 4,
    fill: '#BDF'
  });

  links_layer = svg.append('g');

  nodes_layer = svg.append('g');

  nodes = nodes_layer.selectAll('.node').data(graph_data.nodes);

  nodes.enter().append('circle').attr({
    "class": 'node',
    r: DIAMETER / 2,
    cx: function(node) {
      return node.x;
    },
    cy: function(node) {
      return node.y;
    }
  });

  labels = nodes_layer.selectAll('.label').data(graph_data.nodes);

  labels.enter().append('text').text(function(node) {
    return node.id;
  }).attr({
    "class": 'label',
    dy: '0.35em',
    x: function(node) {
      return node.x;
    },
    y: function(node) {
      return node.y;
    }
  });

  link_thickness = d3.scale.linear().domain([
    0, d3.max(graph_data.links, function(link) {
      return link.weight;
    })
  ]).range([0, DIAMETER * 0.8]);

  links = links_layer.selectAll('.link').data(graph_data.links);

  links.enter().append('path').attr({
    "class": 'link',
    d: function(link) {
      return "M" + link.source.x + " " + link.source.y + " L" + link.target.x + " " + link.target.y;
    },
    'stroke-width': function(link) {
      return link_thickness(link.weight);
    }
  });

}).call(this);

thumbnail.png