an updated look at README.md files from bl.ocks.org that contain links to other bl.ocks with data gathered in early May 2016.
click on a node to view that bl.ock
community detection done with the jLouvain library
source data and scripts used to generate the graph data are at this repository. thanks to @mbostock for removing missing nodes, solitary nodes, self-links, and redundant links. The original dataset contains 2,101 nodes and 8,617 links, and is 1.2 MB. The cleaned dataset contains 1,238 nodes and 2,602 links, and is only 281 KB.
this example also sets the fill-opacity for the nodes to 0.7 so it is more apparent that clusters are in fact comprised of many small, equal-radius individual nodes.
many bl.ocks informed this example:
<html>
<head>
<title>Blocks Graph - Readme Mentions</title>
<meta charset='utf-8' />
<script src='https://d3js.org/d3.v3.min.js'></script>
<script src='https://npmcdn.com/babel-core@5.8.34/browser.min.js'></script>
<script src='jsLouvain.js'></script>
</head>
<body>
<script lang='babel' type='text/babel'>
/* Make the vis fill the page using CSS. */
d3.select('body')
.style({
margin: 0,
position: 'fixed',
top: 0,
right: 0,
bottom: 0,
left: 0
});
d3.select('body').append('div')
.attr('id', 'viz')
.style({
float: 'left',
width: '70%',
position: 'fixed',
top: 0,
right: 0,
bottom: 0,
left: 0
})
d3.select('body').append('div')
.attr('id', 'detail')
.style({
float: 'right',
width: '30%',
position: 'fixed',
top: 0,
right: 0,
bottom: 0,
left: '70%'
})
// Extract the width and height that was computed by CSS.
const vizDiv = document.getElementById('viz');
const width = vizDiv.clientWidth;
const height = vizDiv.clientHeight;
const minSide = d3.min([width, height]);
const xOffset = (width - minSide) / 2;
const yOffset = (height - minSide) / 2;
const detailDiv = document.getElementById('detail');
const detailHeight = detailDiv.clientHeight;
const detailWidth = detailDiv.clientWidth;
const detailSVG = d3.select(detailDiv)
.append('svg')
.attr('width', detailDiv.clientWidth)
.attr('height', detailDiv.clientHeight);
let cardsOnPage = [];
let cardsDisplayed = [];
const nodeHash = {};
// Use the extracted size to set the size of a Canvas element
d3.select(vizDiv).append('canvas')
.attr('width', width)
.attr('height', height)
.style('position', 'absolute');
// Use the extracted size to set the size of a SVG element
d3.select(vizDiv).append('svg')
.attr('width', width)
.attr('height', height)
.classed('main', true)
.style('position', 'absolute');
d3.json('graph.json', function (error, data) {
createNetwork(error, data);
});
// remove thumbnails url data loading for now
// queue()
// .defer(d3.json, 'readme-blocks-graph.json')
// .defer(d3.json, 'thumbnailsHash.json')
// .await((error, data1, data2) => createNetwork(error, data1, data2));
function onlyUnique(value, index, self) {
return self.indexOf(value) === index;
}
function createNetwork(error, graph) {
console.log('graph', graph);
const nodes = [];
const edges = [];
const edgelist = graph.links;
const nodelist = graph.nodes;
edgelist.forEach(edge => {
if (!nodeHash[edge.source]) {
nodeHash[edge.source] = {
id: edge.source,
label: edge.source
};
nodes.push(nodeHash[edge.source]);
}
if (!nodeHash[edge.target]) {
nodeHash[edge.target] = {
id: edge.target,
label: edge.target
};
nodes.push(nodeHash[edge.target]);
}
if (edge /* .weight == 5 */) {
edges.push({
id: `${nodeHash[edge.source].id}-${nodeHash[edge.target].id}`,
source: nodeHash[edge.source],
target: nodeHash[edge.target],
weight: 1 /* edge.weight */
});
}
});
// get some attributes from the nodelist (calculated elsewhere)
// and store them in the nodeHash
nodelist.forEach(node => {
if (nodeHash[node.id]) {
nodeHash[node.id].user = node.user;
nodeHash[node.id].createdAt = node.createdAt;
nodeHash[node.id].updatedAt = node.updatedAt;
nodeHash[node.id].description = node.description;
}
});
// take the attributes now in the nodeHash
// and hang them on the nodes (calculated here from the edgelist)
nodes.forEach(node => {
if (nodeHash[node.id]) {
node.user = nodeHash[node.id].user;
node.createdAt = nodeHash[node.id].createdAt;
node.updatedAt = nodeHash[node.id].updatedAt;
node.description = nodeHash[node.id].description;
}
});
console.log('nodes', nodes);
console.log('edges', edges);
console.log('nodeHash', nodeHash);
createForceNetwork(nodes, edges);
}
function modularityCensus(nodes, edges /* , moduleHash */) {
edges.forEach(edge => {
if (edge.source.module !== edge.target.module) {
edge.border = true;
} else {
edge.border = false;
}
});
nodes.forEach(node => {
const theseEdges = edges.filter(d => d.source === node || d.target === node);
const theseSourceModules = theseEdges.map(d => d.source.module).filter(onlyUnique);
const theseTargetModules = theseEdges.map(d => d.target.module).filter(onlyUnique);
if (theseSourceModules.length > 1 || theseTargetModules.length > 1) {
node.border = true;
} else {
node.border = false;
}
});
}
function createForceNetwork(nodes, edges) {
// create a network from an edgelist
// var colors = d3.scale.ordinal().domain([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]).range(['#996666', '#66CCCC', '#FFFF99', '#CC9999', '#666633', '#993300', '#999966', '#660000', '#996699', '#cc6633', '#ff9966', '#339999', '#6699cc', '#ffcc66', '#ff6600', '#00ccccc']);
const colors = d3.scale.category20();
const nodeData = nodes.map(d => d.id);
const edgeData = edges.map(function (d) {
return {
source: d.source.id,
target: d.target.id,
weight: 1
};
});
console.log('nodeData for jLouvain', nodeData, 'nodes', nodeData.length);
console.log('edgeData for jLouvain', edgeData, 'edges', edgeData.length);
const community = jLouvain().nodes(nodeData).edges(edgeData);
const result = community();
console.log('jLouvain result', result);
nodes.forEach(node => {
node.module = result[node.id];
// console.log('node.module', node.module)
});
modularityCensus(nodes, edges, result);
const force = d3.layout.force().nodes(nodes).links(edges)
.size([minSide, minSide]) // make a square // minSide, minSide
.charge(-100)
.chargeDistance(100)
.linkStrength(2)
.linkDistance(1)
.gravity(0.07);
const nodeEnter = d3.select('svg.main').selectAll('g.node')
.data(nodes, d => d.id)
.enter();
nodeEnter
.append('a')
.attr('xlink:href', d => `//bl.ocks.org/${d.user}/${d.id}`)
.attr('target', '_blank')
.attr('id', d => d.id)
// .attr('target', '_blank')
.append('circle')
.attr('r', 3)
.attr('class', 'foreground')
.style('fill', d => colors(d.module))
.style('fill-opacity', 0.7)
.style('stroke-width', d => {
if (d.border) return '3px';
return '1px';
})
.on('mouseover', d => nodeMouseover(d))
.on('mouseout', () => nodeMouseout());
/*
// draw labels over nodes
nodeEnter.append('text')
.style('text-anchor', 'middle')
.attr('y', 3)
.style('stroke-width', '1px')
.style('stroke-opacity', 0.75)
.style('stroke', 'white')
.style('font-size', '8px')
.text(function (d) {return d.id})
.style('pointer-events', 'none')
nodeEnter.append('text')
.style('text-anchor', 'middle')
.attr('y', 3)
.style('font-size', '8px')
.text(function (d) {return d.id})
.style('pointer-events', 'none')
*/
force.start();
for (let i = 0; i < 200; i++) {
force.tick();
}
// draw the network at each tick
// force.on('tick', updateNetwork);
// after 200 iterations, we say the network
// has stabilized and we stop the
// force layout physics simulation
force.stop();
// now we draw the network
updateNetwork(edges);
// drawVoronoiOverlay();
function updateNetwork(edgesToUpdate) {
// // draw the links
// d3.select('svg.main').selectAll('line')
// .attr('x1', d => d.source.x)
// .attr('y1', d => d.source.y)
// .attr('x2', d => d.target.x)
// .attr('y2', d => d.target.y)
// .attr('transform', 'translate(' + xOffset + ',' + yOffset +')');
const context = d3.select('canvas').node().getContext('2d');
context.clearRect(0, 0, width, height);
context.translate(xOffset, yOffset);
// draw links (or edges, if you prefer)
context.strokeStyle = 'rgba(0, 0, 0, 0.5)';
context.beginPath();
edgesToUpdate.forEach(d => {
context.moveTo(d.source.x, d.source.y);
context.lineTo(d.target.x, d.target.y);
});
context.stroke();
// draw the nodes
d3.select('svg.main').selectAll('circle')
.attr('cx', d => d.x)
.attr('cy', d => d.y)
.attr('transform', `translate(${xOffset}, ${yOffset})`);
}
function drawVoronoiOverlay() {
const rawPoints = [];
nodes.forEach(d => {
rawPoints.push({
x: d.x,
y: d.y,
id: d.id,
user: d.user,
description: d.description
});
});
const voronoi = d3.geom.voronoi();
voronoi
.x(d => d.x)
.y(d => d.y)
.clipExtent([[-10 - xOffset, -10 - yOffset], [width + 10, height + 10]]);
voronoiData = voronoi(rawPoints);
voronoiData = voronoiData.map(function (d, i) {
return {
coordinates: d,
data: rawPoints[i]
};
});
console.log('voronoiData', voronoiData);
const voronoiPaths = d3.select('svg.main').selectAll('path.voronoi')
.data(voronoiData)
.enter()
.insert('path')
.attr('class', 'voronoi')
.style('stroke', 'none')
.style('stroke-width', '1px')
.style('fill', 'white')
.style('fill-opacity', 0)
.attr('d', d => `M${d.coordinates.join('L')}Z`)
.attr('transform', `translate(${xOffset}, ${yOffset})`);
voronoiPaths
.on('mouseover', d => nodeMouseover(d))
.on('click', d => nodeClick(d))
.on('mouseout', () => nodeMouseout());
}
function nodeMouseover(d) {
console.log('nodeHash', nodeHash);
// allow nodeMousever to be called in different contexts
// either from the node circle or from the Voronoi path
let id;
let user;
let description;
const dH = 30;
if (typeof d.data === 'undefined') {
id = d.id;
user = nodeHash[d.id].user;
description = nodeHash[d.id].description;
}
else {
id = d.data.id;
user = d.data.user;
d.data.description;
}
const blockUrl = `//bl.ocks.org/${user}/${id}`
// generate nice text to display on the small canvas below the thumbnail image
let blockTitleText;
if (
['undefined', 'null'].indexOf(String(user)) === -1 &&
['undefined', 'null'].indexOf(String(description)) === -1
) {
blockTitleText = `${user} | ${description}`
}
if (
['undefined', 'null'].indexOf(String(user)) === -1 &&
['undefined', 'null'].indexOf(String(description)) > -1
) {
blockTitleText = user;
}
if (
['undefined', 'null'].indexOf(String(user)) > -1 &&
['undefined', 'null'].indexOf(String(description)) === -1
) {
blockTitleText = description;
}
if (
['undefined', 'null'].indexOf(String(user)) > -1 &&
['undefined', 'null'].indexOf(String(description)) > -1
) {
blockTitleText = '';
}
console.log(blockUrl);
console.log(blockTitleText);
// const cardDiv = d3.select(detailDiv).append('div')
// .attr('id', `card${id}`)
// .append('a')
// .attr('xlink:href', d => `//bl.ocks.org/${user}/${id}`)
// .innerHTML(blockTitleText);
//if (cardsDisplayed.length > 10) {
// d3.selectAll('.cards')
// .attr('transform', `translate(0,${15 * (cardsOnPage.length-1)})`);
//}
// draw a rectangle
const detailG = detailSVG.append('a')
.attr('xlink:href', blockUrl)
.attr('target', '_blank')
.attr('id', `card${id}`)
.classed('cards', true)
.append('rect')
//.classed('cards', true)
.attr('id', `card${id}`)
.attr('x', 0)
.attr('y', 5 + dH * cardsOnPage.length)
.attr('height', dH)
.attr('width', detailDiv.clientWidth)
.style('stroke-width', 1)
.style('stroke', 'white')
.style('fill', 'lightgray')
.style('fill-opacity', .4)
.attr('rx', 4)
.attr('ry', 4);
// draw text on the screen
detailSVG.append('text')
.attr('x', 10)
.attr('y', 5 + dH * cardsOnPage.length)
.classed('cards', true)
.attr('id', `card${id}`)
.style('fill', 'black')
.style('font-size', '16px')
.attr('dy', '20px')
.attr('text-anchor', 'start')
.style('pointer-events', 'none')
.text(blockTitleText);
console.log('cardsOnPage', cardsOnPage);
console.log('cardsOnPage.length', cardsOnPage.length);
if (false/*cardsDisplayed.length > 10*/) {
const lastCardId = cardsOnPage[cardsOnPage.length - 1];
const firstCardId = cardsOnPage[0];
const cardSelector = `div#card${firstCardId}`.replace(/[,.]/g, '');
d3.select(cardSelector)
.remove();
// d3.selectAll('.cards')
// .attr('transform', `translate(0,-15)`);
//cardsOnPage.pop();
cardsOnPage.shift();
//if(cardsOnPage.indexOf(id) > -1) cardsOnPage = removeByValue(cardsOnPage, id);
}
cardsOnPage.push(id);
cardsDisplayed.push(id);
d3.select(vizDiv).select('svg').append('text')
.attr('x', 100)
.attr('y', 100)
.classed('titleText', true)
.style('fill', 'black')
.style('fill-opacity', 0.8)
.style('font-size', '30px')
.style('font-weight', 600)
.attr('dy', '0px')
.attr('text-anchor', 'start')
.style('pointer-events', 'none')
.text(blockTitleText);
}
function nodeMouseout() {
d3.selectAll('.titleText')
.remove();
}
// //stackoverflow.com/a/11223909/1732222
function ImageExist(url)
{
var img = new Image();
img.src = url;
return img.height != 0;
}
// //stackoverflow.com/a/3955096/1732222
function removeByValue(arr) {
var what, a = arguments, L = a.length, ax;
while (L > 1 && arr.length) {
what = a[--L];
while ((ax= arr.indexOf(what)) !== -1) {
arr.splice(ax, 1);
}
}
return arr;
}
function nodeClick(d) {
const user = d.data.user;
const id = d.data.id;
const blockUrl = `//bl.ocks.org/${user}/${id}`
openInNewTab(blockUrl);
}
// //stackoverflow.com/a/11384018/1732222
function openInNewTab(url) {
const win = window.open(url, '_blank');
win.focus();
}
}
</script>
</body>
</html>/*
Author: Corneliu S. (github.com/upphiminn)
This is a javascript implementation of the Louvain
community detection algorithm (http://arxiv.org/abs/0803.0476)
Based on https://bitbucket.org/taynaud/python-louvain/overview
*/
(function(){
jLouvain = function(){
//Constants
var __PASS_MAX = -1
var __MIN = 0.0000001
//Local vars
var original_graph_nodes;
var original_graph_edges;
var original_graph = {};
var partition_init;
//Helpers
function make_set(array){
var set = {};
array.forEach(function(d,i){
set[d] = true;
});
return Object.keys(set);
};
function obj_values(obj){
var vals = [];
for( var key in obj ) {
if ( obj.hasOwnProperty(key) ) {
vals.push(obj[key]);
}
}
return vals;
};
function get_degree_for_node(graph, node){
var neighbours = graph._assoc_mat[node] ? Object.keys(graph._assoc_mat[node]) : [];
var weight = 0;
neighbours.forEach(function(neighbour,i){
var value = graph._assoc_mat[node][neighbour] || 1;
if(node == neighbour)
value *= 2;
weight += value;
});
return weight;
};
function get_neighbours_of_node(graph, node){
if(typeof graph._assoc_mat[node] == 'undefined')
return [];
var neighbours = Object.keys(graph._assoc_mat[node]);
return neighbours;
}
function get_edge_weight(graph, node1, node2){
return graph._assoc_mat[node1] ? graph._assoc_mat[node1][node2] : undefined;
}
function get_graph_size(graph){
var size = 0;
graph.edges.forEach(function(edge){
size += edge.weight;
});
return size;
}
function add_edge_to_graph(graph, edge){
update_assoc_mat(graph, edge);
var edge_index = graph.edges.map(function(d){
return d.source+'_'+d.target;
}).indexOf(edge.source+'_'+edge.target);
if(edge_index != -1)
graph.edges[edge_index].weight = edge.weight;
else
graph.edges.push(edge);
}
function make_assoc_mat(edge_list){
var mat = {};
edge_list.forEach(function(edge, i){
mat[edge.source] = mat[edge.source] || {};
mat[edge.source][edge.target] = edge.weight;
mat[edge.target] = mat[edge.target] || {};
mat[edge.target][edge.source] = edge.weight;
});
return mat;
}
function update_assoc_mat(graph, edge){
graph._assoc_mat[edge.source] = graph._assoc_mat[edge.source] || {};
graph._assoc_mat[edge.source][edge.target] = edge.weight;
graph._assoc_mat[edge.target] = graph._assoc_mat[edge.target] || {};
graph._assoc_mat[edge.target][edge.source] = edge.weight;
}
function clone(obj){
if(obj == null || typeof(obj) != 'object')
return obj;
var temp = obj.constructor();
for(var key in obj)
temp[key] = clone(obj[key]);
return temp;
}
//Core-Algorithm Related
function init_status(graph, status, part){
status['nodes_to_com'] = {};
status['total_weight'] = 0;
status['internals'] = {};
status['degrees'] = {};
status['gdegrees'] = {};
status['loops'] = {};
status['total_weight'] = get_graph_size(graph);
if(typeof part == 'undefined'){
graph.nodes.forEach(function(node,i){
status.nodes_to_com[node] = i;
var deg = get_degree_for_node(graph, node);
if (deg < 0)
throw 'Bad graph type, use positive weights!';
status.degrees[i] = deg;
status.gdegrees[node] = deg;
status.loops[node] = get_edge_weight(graph, node, node) || 0;
status.internals[i] = status.loops[node];
});
}else{
graph.nodes.forEach(function(node,i){
var com = part[node];
status.nodes_to_com[node] = com;
var deg = get_degree_for_node(graph, node);
status.degrees[com] = (status.degrees[com] || 0) + deg;
status.gdegrees[node] = deg;
var inc = 0.0;
var neighbours = get_neighbours_of_node(graph, node);
neighbours.forEach(function(neighbour, i){
var weight = graph._assoc_mat[node][neighbour];
if (weight <= 0){
throw "Bad graph type, use positive weights";
}
if(part[neighbour] == com){
if (neighbour == node){
inc += weight;
}else{
inc += weight/2.0;
}
}
});
status.internals[com] = (status.internals[com] || 0) + inc;
});
}
}
function __modularity(status){
var links = status.total_weight;
var result = 0.0;
var communities = make_set(obj_values(status.nodes_to_com));
communities.forEach(function(com,i){
var in_degree = status.internals[com] || 0 ;
var degree = status.degrees[com] || 0 ;
if(links > 0){
result = result + in_degree / links - Math.pow((degree / (2.0*links)), 2);
}
});
return result;
}
function __neighcom(node, graph, status){
// compute the communities in the neighb. of the node, with the graph given by
// node_to_com
var weights = {};
var neighboorhood = get_neighbours_of_node(graph, node);//make iterable;
neighboorhood.forEach(function(neighbour, i){
if(neighbour != node){
var weight = graph._assoc_mat[node][neighbour] || 1;
var neighbourcom = status.nodes_to_com[neighbour];
weights[neighbourcom] = (weights[neighbourcom] || 0) + weight;
}
});
return weights;
}
function __insert(node, com, weight, status){
//insert node into com and modify status
status.nodes_to_com[node] = +com;
status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node]||0);
status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node]||0);
}
function __remove(node, com, weight, status){
//remove node from com and modify status
status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0));
status.internals[com] = ((status.internals[com] || 0) - weight -(status.loops[node] ||0));
status.nodes_to_com[node] = -1;
}
function __renumber(dict){
var count = 0;
var ret = clone(dict); //deep copy :)
var new_values = {};
var dict_keys = Object.keys(dict);
dict_keys.forEach(function(key){
var value = dict[key];
var new_value = typeof new_values[value] =='undefined' ? -1 : new_values[value];
if(new_value == -1){
new_values[value] = count;
new_value = count;
count = count + 1;
}
ret[key] = new_value;
});
return ret;
}
function __one_level(graph, status){
//Compute one level of the Communities Dendogram.
var modif = true,
nb_pass_done = 0,
cur_mod = __modularity(status),
new_mod = cur_mod;
while (modif && nb_pass_done != __PASS_MAX){
cur_mod = new_mod;
modif = false;
nb_pass_done += 1
graph.nodes.forEach(function(node,i){
var com_node = status.nodes_to_com[node];
var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0);
var neigh_communities = __neighcom(node, graph, status);
__remove(node, com_node, (neigh_communities[com_node] || 0.0), status);
var best_com = com_node;
var best_increase = 0;
var neigh_communities_entries = Object.keys(neigh_communities);//make iterable;
neigh_communities_entries.forEach(function(com,i){
var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw;
if (incr > best_increase){
best_increase = incr;
best_com = com;
}
});
__insert(node, best_com, neigh_communities[best_com] || 0, status);
if(best_com != com_node)
modif = true;
});
new_mod = __modularity(status);
if(new_mod - cur_mod < __MIN)
break;
}
}
function induced_graph(partition, graph){
var ret = {nodes:[], edges:[], _assoc_mat: {}};
var w_prec, weight;
//add nodes from partition values
var partition_values = obj_values(partition);
ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set
graph.edges.forEach(function(edge,i){
weight = edge.weight || 1;
var com1 = partition[edge.source];
var com2 = partition[edge.target];
w_prec = (get_edge_weight(ret, com1, com2) || 0);
var new_weight = (w_prec + weight);
add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight});
});
return ret;
}
function partition_at_level(dendogram, level){
var partition = clone(dendogram[0]);
for(var i = 1; i < level + 1; i++ )
Object.keys(partition).forEach(function(key,j){
var node = key;
var com = partition[key];
partition[node] = dendogram[i][com];
});
return partition;
}
function generate_dendogram(graph, part_init){
if(graph.edges.length == 0){
var part = {};
graph.nodes.forEach(function(node,i){
part[node] = node;
});
return part;
}
var status = {};
init_status(original_graph, status, part_init);
var mod = __modularity(status);
var status_list = [];
__one_level(original_graph, status);
var new_mod = __modularity(status);
var partition = __renumber(status.nodes_to_com);
status_list.push(partition);
mod = new_mod;
var current_graph = induced_graph(partition, original_graph);
init_status(current_graph, status);
while (true){
__one_level(current_graph, status);
new_mod = __modularity(status);
if(new_mod - mod < __MIN)
break;
partition = __renumber(status.nodes_to_com);
status_list.push(partition);
mod = new_mod;
current_graph = induced_graph(partition, current_graph);
init_status(current_graph, status);
}
return status_list;
}
var core = function(){
var status = {};
var dendogram = generate_dendogram(original_graph, partition_init);
return partition_at_level(dendogram, dendogram.length - 1);
};
core.nodes = function(nds){
if(arguments.length > 0){
original_graph_nodes = nds;
}
return core;
};
core.edges = function(edgs){
if(typeof original_graph_nodes == 'undefined')
throw 'Please provide the graph nodes first!';
if(arguments.length > 0){
original_graph_edges = edgs;
var assoc_mat = make_assoc_mat(edgs);
original_graph = { 'nodes': original_graph_nodes,
'edges': original_graph_edges,
'_assoc_mat': assoc_mat };
}
return core;
};
core.partition_init = function(prttn){
if(arguments.length > 0){
partition_init = prttn;
}
return core;
};
return core;
}
})();