Skip to content

Instantly share code, notes, and snippets.

@nitaku
Last active August 29, 2015 14:04
Show Gist options
  • Save nitaku/d5fc7956ba6896330ea1 to your computer and use it in GitHub Desktop.
Save nitaku/d5fc7956ba6896330ea1 to your computer and use it in GitHub Desktop.
Node-link polar layout with centrality (eigenvector)

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)
# 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)
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;
}
<!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>
(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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment