an updated look at README.md files from bl.ocks.org that contain links to other bl.ocks. These 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
a lineage of bl.ocks that informed this idea:
<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('readme-blocks-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, graphContainer) {
console.log('graphContainer', graphContainer);
const nodes = [];
const edges = [];
const edgelist = graphContainer.graph.edges;
const nodelist = graphContainer.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('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', '60px')
.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;
}
})();