Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/firm.csv

Last active March 16, 2016 15:50
Show Gist options
  • Save emeeks/3a54620a4751a7d68c1e to your computer and use it in GitHub Desktop.
Save emeeks/3a54620a4751a7d68c1e to your computer and use it in GitHub Desktop.
Download ZIP
Example of d3.layout.forceInABox
Raw
readme.md

An implementation of d3.layout.forceInABox which implements a method to separate nodes in a network visually based on some kind of group membership.

In this case, the group is the community membership of the node as determined by Louvain modularity using jLouvain.js.

Raw
firm.csv
source target weight
1 3 5
1 8 3
1 9 3
1 12 3
1 15 2
1 23 3
1 26 2
1 37 2
1 46 2
2 1 1
2 4 2
2 5 1
2 6 3
2 7 5
2 8 4
2 10 1
2 11 5
2 12 1
2 13 4
2 14 4
2 16 2
2 18 3
2 19 2
2 20 5
2 21 1
2 22 3
2 25 3
2 26 1
2 27 4
2 28 4
2 29 5
2 31 2
2 33 2
2 34 3
2 35 5
2 37 1
2 38 4
2 41 3
3 1 4
3 4 1
3 8 1
3 9 4
3 12 4
3 22 1
3 31 1
3 32 4
3 33 2
3 37 1
3 46 4
4 8 3
4 11 2
4 20 2
4 32 3
4 33 3
4 40 5
5 2 1
5 6 5
5 7 1
5 13 1
5 14 2
5 17 1
5 18 1
5 19 5
5 20 3
5 21 2
5 23 3
5 25 3
5 26 5
5 27 2
5 28 1
5 29 3
5 34 1
5 36 3
5 38 1
5 39 4
5 44 3
5 45 5
6 2 1
6 5 3
6 7 1
6 11 1
6 13 1
6 14 1
6 17 3
6 19 4
6 20 2
6 21 3
6 23 3
6 25 5
6 26 5
6 27 1
6 28 5
6 29 1
6 35 1
6 36 5
6 38 1
6 39 5
6 44 5
6 45 4
7 2 5
7 8 3
7 11 3
7 13 3
7 14 5
7 19 2
7 20 4
7 23 2
7 26 2
7 27 2
7 28 2
7 29 4
7 34 4
7 35 5
7 38 2
7 45 2
8 1 4
8 2 3
8 3 2
8 4 4
8 7 3
8 9 3
8 10 3
8 11 1
8 12 4
8 15 2
8 16 2
8 18 1
8 19 1
8 20 2
8 22 4
8 29 1
8 31 5
8 32 4
8 33 5
8 34 3
8 37 2
8 38 2
8 40 2
8 41 3
8 42 1
8 43 1
8 45 1
8 46 1
9 1 3
9 3 2
9 4 1
9 8 1
9 12 1
9 15 1
9 17 5
9 18 1
9 26 1
9 31 1
9 32 2
9 33 1
9 37 1
9 40 1
9 46 1
10 1 3
10 2 1
10 4 1
10 8 4
10 9 5
10 11 1
10 12 1
10 14 1
10 17 5
10 18 1
10 19 1
10 20 2
10 23 2
10 28 2
10 31 2
10 33 1
10 34 1
10 37 2
10 38 3
10 40 2
10 41 2
10 42 1
10 43 2
10 44 1
10 45 1
11 2 5
11 20 4
11 38 3
11 45 4
12 1 3
12 2 1
12 3 2
12 4 1
12 5 1
12 6 1
12 7 1
12 8 3
12 9 2
12 10 1
12 11 1
12 13 1
12 14 1
12 15 1
12 16 1
12 17 1
12 18 1
12 19 1
12 20 1
12 21 1
12 22 5
12 23 1
12 24 1
12 25 1
12 26 1
12 27 1
12 28 1
12 29 1
12 30 1
12 31 2
12 32 2
12 33 5
12 34 1
12 35 1
12 36 1
12 37 2
12 38 1
12 39 1
12 40 1
12 41 2
12 42 1
12 43 1
12 44 1
12 45 1
12 46 5
13 2 3
13 5 1
13 6 1
13 7 2
13 11 1
13 17 1
13 18 2
13 19 2
13 20 2
13 21 1
13 23 1
13 25 1
13 26 1
13 27 2
13 28 1
13 29 3
13 34 1
13 35 1
13 38 1
13 44 1
13 45 1
14 2 4
14 5 1
14 6 1
14 7 2
14 8 1
14 11 1
14 19 1
14 20 3
14 22 1
14 23 1
14 27 1
14 28 1
14 31 1
14 33 1
14 35 1
14 38 2
14 41 1
14 45 1
16 1 1
16 2 1
16 3 1
16 4 1
16 5 1
16 6 1
16 7 1
16 8 1
16 9 1
16 10 1
16 11 1
16 12 1
16 13 1
16 14 1
16 15 1
16 17 1
16 18 1
16 19 1
16 20 1
16 21 1
16 22 1
16 23 1
16 24 1
16 25 1
16 26 1
16 27 1
16 28 1
16 29 1
16 30 1
16 31 1
16 32 1
16 33 1
16 34 1
16 35 1
16 36 1
16 37 1
16 38 1
16 39 1
16 40 1
16 41 1
16 42 1
16 43 1
16 44 1
16 45 1
16 46 1
17 5 1
17 6 2
17 10 5
17 13 1
17 19 3
17 20 1
17 21 1
17 23 4
17 25 2
17 26 3
17 28 3
17 29 3
17 36 2
17 38 1
17 39 2
17 44 3
17 45 3
18 1 1
18 2 4
18 5 2
18 7 2
18 8 2
18 9 1
18 10 1
18 11 2
18 13 5
18 15 1
18 16 1
18 20 4
18 22 2
18 25 4
18 26 2
18 27 3
18 28 2
18 29 2
18 31 3
18 33 3
18 34 3
18 35 1
18 37 2
18 38 2
18 40 2
19 2 3
19 5 5
19 6 5
19 7 3
19 11 2
19 13 3
19 14 2
19 17 3
19 20 2
19 21 2
19 25 3
19 26 5
19 27 2
19 28 3
19 29 2
19 36 5
19 38 3
19 39 5
19 44 5
19 45 5
20 1 2
20 2 3
20 4 2
20 5 2
20 6 2
20 7 3
20 8 4
20 9 1
20 10 2
20 11 4
20 12 2
20 13 5
20 14 4
20 17 1
20 18 4
20 19 3
20 21 1
20 22 2
20 23 3
20 25 3
20 26 2
20 27 4
20 28 4
20 29 4
20 31 3
20 34 3
20 35 2
20 36 2
20 38 4
20 41 2
20 43 2
20 44 3
20 45 5
21 2 2
21 6 3
21 17 4
21 19 2
21 20 3
21 23 2
21 25 2
21 26 3
21 27 2
21 28 3
21 29 4
21 36 2
21 39 2
21 44 4
21 45 4
22 1 1
22 2 2
22 3 1
22 4 2
22 5 1
22 6 1
22 7 1
22 8 3
22 9 1
22 10 1
22 11 2
22 12 5
22 13 1
22 14 1
22 15 5
22 16 2
22 17 1
22 18 2
22 19 1
22 20 1
22 21 1
22 23 1
22 24 1
22 25 1
22 26 1
22 27 1
22 28 1
22 29 1
22 30 1
22 31 2
22 32 2
22 33 5
22 34 2
22 35 1
22 36 1
22 37 1
22 38 4
22 39 1
22 40 5
22 41 1
22 42 1
22 43 1
22 44 1
22 45 2
22 46 2
23 1 2
23 2 1
23 5 3
23 6 3
23 7 1
23 10 3
23 11 2
23 13 1
23 14 1
23 17 4
23 19 3
23 20 3
23 21 1
23 25 2
23 26 4
23 27 1
23 28 3
23 29 4
23 31 1
23 34 1
23 35 1
23 36 5
23 38 2
23 39 4
23 44 4
23 45 2
25 2 2
25 5 2
25 6 5
25 7 1
25 11 1
25 13 1
25 17 1
25 18 2
25 19 4
25 20 3
25 23 3
25 26 4
25 27 2
25 28 3
25 29 1
25 35 1
25 36 3
25 39 3
25 44 2
25 45 3
26 1 1
26 2 1
26 5 5
26 6 5
26 7 1
26 9 1
26 11 2
26 13 1
26 17 4
26 18 1
26 19 5
26 20 2
26 21 2
26 23 5
26 25 5
26 27 2
26 28 4
26 29 2
26 31 1
26 34 1
26 35 1
26 36 5
26 38 2
26 39 5
26 44 5
26 45 5
27 2 4
27 5 2
27 6 2
27 7 2
27 11 1
27 13 5
27 14 3
27 17 1
27 18 3
27 19 2
27 20 4
27 21 1
27 23 1
27 25 3
27 26 2
27 28 2
27 29 4
27 34 1
27 35 5
27 36 1
27 38 1
27 39 1
27 44 1
27 45 3
28 2 3
28 5 2
28 6 5
28 7 2
28 10 2
28 11 2
28 13 2
28 17 4
28 18 3
28 19 3
28 20 3
28 21 2
28 23 4
28 25 2
28 26 3
28 27 2
28 29 3
28 36 3
28 38 2
28 39 2
28 44 4
28 45 3
29 2 4
29 4 1
29 5 3
29 6 1
29 7 4
29 8 1
29 11 1
29 13 3
29 14 1
29 17 1
29 18 1
29 19 1
29 20 4
29 21 2
29 23 4
29 25 1
29 26 1
29 27 3
29 28 3
29 34 1
29 35 1
29 36 1
29 38 1
29 44 2
29 45 1
30 24 1
31 1 2
31 2 2
31 3 1
31 4 3
31 8 5
31 9 1
31 10 2
31 12 2
31 16 2
31 18 3
31 20 3
31 22 2
31 23 2
31 32 2
31 34 2
31 37 1
31 38 3
31 40 3
31 41 2
31 43 1
31 45 2
32 1 2
32 3 2
32 4 5
32 8 2
32 9 2
32 12 1
32 31 1
32 33 3
32 34 2
32 37 1
32 40 5
32 41 1
32 46 1
33 1 2
33 2 2
33 4 5
33 8 5
33 9 2
33 10 2
33 11 1
33 12 5
33 14 1
33 15 3
33 16 3
33 18 3
33 20 1
33 22 5
33 31 3
33 32 3
33 34 3
33 37 3
33 38 2
33 40 5
33 43 2
34 1 1
34 2 2
34 5 1
34 6 1
34 7 1
34 8 2
34 13 1
34 16 1
34 18 1
34 19 1
34 20 1
34 22 1
34 23 1
34 25 1
34 26 1
34 27 1
34 28 1
34 29 1
34 31 3
34 32 1
34 33 4
34 35 1
34 37 2
34 38 2
34 40 1
34 42 5
34 43 1
35 2 3
35 13 2
35 18 2
35 27 4
35 29 2
35 39 2
36 2 1
36 5 3
36 6 5
36 17 3
36 18 1
36 19 4
36 20 1
36 21 1
36 23 5
36 25 4
36 26 5
36 28 4
36 29 2
36 39 4
36 44 5
36 45 5
37 1 2
37 2 1
37 8 2
37 9 1
37 10 2
37 12 2
37 18 1
37 31 2
37 32 1
37 33 1
37 34 2
37 40 1
37 43 1
38 2 5
38 4 2
38 6 2
38 7 4
38 8 2
38 11 3
38 13 2
38 14 4
38 18 1
38 19 2
38 20 3
38 22 5
38 23 3
38 26 2
38 28 1
38 29 3
38 31 3
38 33 3
38 34 2
38 35 5
38 41 4
38 44 1
38 45 2
39 5 3
39 6 5
39 13 1
39 17 1
39 19 5
39 23 4
39 25 2
39 26 4
39 28 2
39 36 3
39 44 4
39 45 5
40 1 1
40 2 1
40 4 5
40 8 3
40 9 1
40 12 1
40 15 3
40 16 2
40 18 1
40 20 1
40 22 3
40 31 2
40 32 5
40 33 5
40 34 2
40 37 2
40 43 1
41 1 2
41 2 2
41 8 3
41 10 5
41 12 2
41 14 2
41 20 2
41 38 3
41 43 2
42 8 1
42 10 1
42 28 1
42 31 1
42 33 1
42 34 4
42 37 1
42 41 1
42 43 1
42 45 1
43 8 2
43 12 2
43 31 1
43 33 2
43 34 1
44 1 1
44 2 1
44 5 3
44 6 5
44 7 1
44 8 1
44 11 1
44 13 1
44 17 3
44 19 5
44 20 2
44 21 2
44 23 3
44 25 2
44 26 4
44 28 2
44 33 1
44 34 1
44 35 1
44 36 4
44 38 1
44 39 4
44 42 1
44 43 1
44 45 3
45 1 1
45 2 2
45 4 1
45 5 5
45 6 5
45 7 2
45 8 1
45 9 1
45 10 1
45 11 3
45 12 2
45 13 1
45 14 2
45 17 4
45 18 2
45 19 4
45 20 4
45 21 3
45 22 1
45 23 3
45 25 4
45 26 5
45 27 2
45 28 3
45 29 3
45 31 3
45 33 1
45 34 1
45 35 1
45 36 5
45 38 2
45 42 1
45 44 4
46 1 3
46 3 4
46 8 1
46 9 3
46 12 5
46 22 1
46 32 2
46 33 2
46 34 2
46 37 1
46 43 1
Raw
forceInABox.js
/* global d3 */
/* jslint browser: true, devel: true, indent: 4, multistr: true */
d3.layout.forceInABox = function () {
"use strict";
var force = d3.layout.force(),
tree,
foci = {},
oldStart = force.start,
oldLinkStrength = force.linkStrength(),
oldGravity = force.gravity(),
treeMapNodes = [],
groupBy = function (d) {return d["cluster"]},
enableGrouping = true,
gravityToFoci = 0.1,
gravityOverall = 0.01,
linkStrengthInterCluster = 0.05;
// force.gravity = function(x) {
// if (!arguments.length) return oldGravity;
// oldGravity = +x;
// return force;
// };
force.groupBy = function (x) {
if (!arguments.length) return groupBy;
if (typeof x === "string") {
x = function (d) {return d[x]; };
return force;
}
groupBy = x;
return force;
};
var update = function () {
if (enableGrouping) {
force.gravity(gravityOverall);
} else {
force.gravity(oldGravity);
}
};
force.enableGrouping = function (x) {
if (!arguments.length) return enableGrouping;
enableGrouping = x;
update();
return force;
};
force.gravityToFoci = function (x) {
if (!arguments.length) return gravityToFoci;
gravityToFoci = x;
return force;
};
force.gravityOverall = function (x) {
if (!arguments.length) return gravityOverall;
gravityOverall = x;
return force;
};
force.linkStrengthInterCluster = function (x) {
if (!arguments.length) return linkStrengthInterCluster;
linkStrengthInterCluster = x;
return force;
};
force.linkStrength(function (e) {
if (!enableGrouping || groupBy(e.source) === groupBy(e.target)) {
if (typeof(oldLinkStrength)==="function") {
return oldLinkStrength(e);
} else {
return oldLinkStrength;
}
} else {
if (typeof(linkStrengthInterCluster)==="function") {
return linkStrengthInterCluster(e);
} else {
return linkStrengthInterCluster;
}
}
});
function computeClustersCounts(nodes) {
var clustersCounts = d3.map();
nodes.forEach(function (d) {
if (!clustersCounts.has(groupBy(d))) {
clustersCounts.set(groupBy(d), 0);
}
});
nodes.forEach(function (d) {
// if (!d.show) { return; }
clustersCounts.set(groupBy(d), clustersCounts.get(groupBy(d)) + 1);
});
return clustersCounts;
}
function getGroupsTree() {
var children = [],
totalSize = 0,
clustersList,
c, i, size, clustersCounts;
clustersCounts=computeClustersCounts(force.nodes());
//map.keys() is really slow, it's crucial to have it outside the loop
clustersList = clustersCounts.keys();
for (i = 0; i< clustersList.length ; i+=1) {
c = clustersList[i];
size = clustersCounts.get(c);
children.push({id : c, size :size });
totalSize += size;
}
return {id: "clustersTree", size: totalSize, children : children};
}
force.recompute = function () {
var treemap = d3.layout.treemap()
.size(force.size())
.sort(function (p, q) { return d3.ascending(p.size, q.size); })
.value(function (d) { return d.size; });
tree = getGroupsTree();
treeMapNodes = treemap.nodes(tree);
//compute foci
foci.none = {x : 0, y : 0};
treeMapNodes.forEach(function (d) {
foci[d.id] = {
x : (d.x + d.dx / 2),
y : (d.y + d.dy / 2)
};
});
// Draw the treemap
return force;
};
force.drawTreemap = function (container) {
container.selectAll("rect.cell").remove();
container.selectAll("rect.cell")
.data(treeMapNodes)
.enter().append("svg:rect")
.attr("class", "cell")
.attr("x", function (d) { return d.x; })
.attr("y", function (d) { return d.y; })
.attr("width", function (d) { return d.dx; })
.attr("height", function (d) { return d.dy; });
return force;
};
force.deleteTreemap = function (container) {
container.selectAll("rect.cell").remove();
return force;
};
force.onTick = function (e) {
if (!enableGrouping) {
return force;
}
var k;
k = force.gravityToFoci() * e.alpha;
force.nodes().forEach(function (o) {
if (!foci.hasOwnProperty(groupBy(o))) { return; }
o.y += (foci[groupBy(o)].y - o.y) * k;
o.x += (foci[groupBy(o)].x - o.x) * k;
});
return force;
};
force.start = function () {
update();
oldStart();
if (enableGrouping) {
force.recompute();
}
return force;
};
return force;
};
Raw
index.html
<html>
<head>
<title>Community Grid</title>
<meta charset="utf-8" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.16/d3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="jsLouvain.js" type="text/JavaScript"></script>
<script src="forceInABox.js" type="text/JavaScript"></script>
</head>
<style>
svg {
height: 500px;
width: 500px;
border: 1px solid gray;
}
</style>
<body>
<div id="viz">
<svg class="main">
</svg>
</div>
</body>
<footer>
<script>
d3.csv("firm.csv",function(error,data) {createNetwork(data)});
function onlyUnique(value, index, self) {
return self.indexOf(value) === index;
}
function createNetwork(edgelist) {
var nodeHash = {};
var nodes = [];
var edges = [];
edgelist.forEach(function (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: edge.weight});
}
});
createForceNetwork(nodes, edges);
}
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"]);
var node_data = nodes.map(function (d) {return d.id});
var edge_data = edges.map(function (d) {return {source: d.source.id, target: d.target.id, weight: 1}; });
var community = jLouvain().nodes(node_data).edges(edge_data);
var result = community();
nodes.forEach(function (node) {
node.module = result[node.id]
});
var force = d3.layout.forceInABox()
.charge(-120)
.linkDistance(50)
.linkStrengthInterCluster(0.01)
.gravityToFoci(0.2)
.gravityOverall(0.05)
.size([500, 500])
.groupBy(function (d) {return d.module});
force
.nodes(nodes)
.links(edges)
.on("tick", updateGraph);
var edgeEnter = d3.select("svg.main").selectAll("g.edge")
.data(edges, function (d) {return d.id})
.enter()
.append("g")
.attr("class", "edge");
edgeEnter
.append("line")
.style("stroke-width", "1px")
.style("stroke", "black")
.style("pointer-events", "none");
var nodeEnter = d3.select("svg.main")
.selectAll("g.node")
.data(nodes, function (d) {return d.id})
.enter()
.append("g")
.attr("class", "node")
.call(force.drag());
nodeEnter.append("circle")
.attr("r", 8)
.style("fill", function (d) {return colors(d.module)})
.style("stroke", "black")
.style("stroke-width", "1px")
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();
function updateGraph(e) {
force.onTick(e);
d3.selectAll("line")
.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
d3.selectAll("g.node")
.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; });
}
}
</script>
</footer>
</html>
Raw
jsLouvain.js
/*
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;
}
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment