Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nitaku/ba30b3588093e58200b1 to your computer and use it in GitHub Desktop.
Save nitaku/ba30b3588093e58200b1 to your computer and use it in GitHub Desktop.
Download ZIP
Node-link polar layout with centrality (weighted eigenvector)
Raw
README.md

An improvement upon the previous experiment. This time, a variant of eigenvector centrality that takes into account the weights of the links is computed, yielding a very different diagram.

In order to do that, the network's adjacency matrix is populated with weights in place of binary (connected / not connected) information. Computing the centrality measure using this matrix is sufficient to obtain a result that takes topology and weights into account, as discussed in Newman 2004 (alongwith other analysis methods for weighted networks).

Raw
index.coffee
# data
graph_data = {
nodes: [
{id: 'A', centrality: {eigenvector: 0.5128343}},
{id: 'B', centrality: {eigenvector: 0.3408974}},
{id: 'C', centrality: {eigenvector: 0.3216734}},
{id: 'D', centrality: {eigenvector: 0.5535792}},
{id: 'E', centrality: {eigenvector: 0.2333755}},
{id: 'F', centrality: {eigenvector: 0.2680001}},
{id: 'G', centrality: {eigenvector: 0.2908231}}
],
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.6])
.range([330, 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)
fill: 'none'
stroke: '#8AC'
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: distance(0.5)
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)
Raw
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;
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="description" content="Node-link polar layout with centrality (weighted eigenvector)" />
<title>Node-link polar layout with centrality (weighted eigenvector)</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>
Raw
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: {
eigenvector: 0.5128343
}
}, {
id: 'B',
centrality: {
eigenvector: 0.3408974
}
}, {
id: 'C',
centrality: {
eigenvector: 0.3216734
}
}, {
id: 'D',
centrality: {
eigenvector: 0.5535792
}
}, {
id: 'E',
centrality: {
eigenvector: 0.2333755
}
}, {
id: 'F',
centrality: {
eigenvector: 0.2680001
}
}, {
id: 'G',
centrality: {
eigenvector: 0.2908231
}
}
],
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.6]).range([330, 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),
fill: 'none',
stroke: '#8AC'
});
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: distance(0.5),
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment