Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/firm.csv

Last active March 17, 2016 02: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 emeeks/39fea1d900964379416b to your computer and use it in GitHub Desktop.
Save emeeks/39fea1d900964379416b to your computer and use it in GitHub Desktop.
Download ZIP
Networks - Graphs 5
Raw
readme.md

Graph Example 5 for How to Create Effective Network Data Visualization

In this example, the position of the modularity nodes on the mini-map is determined by the average position of the nodes that make them up. Mousing over a node on the mini-map will highlight the node in the main network data visualization.

Drag the regular nodes to watch the change in position of the modularity nodes in the mini-map.

This example relies on the jLouvain library to calculate community structure.

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
index.html
<html>
<head>
<title>Linked modularity minimap</title>
<meta charset="utf-8" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="jsLouvain.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 == 4) {
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 modularityCensus(nodes, edges, moduleHash) {
edges.forEach(function (edge) {
if (edge.source.module !== edge.target.module) {
edge.border = true;
}
else {
edge.border = false;
}
});
nodes.forEach(function (node) {
var theseEdges = edges.filter(function(d) {return d.source === node || d.target === node});
var theseSourceModules = theseEdges.map(function (d) {return d.source.module}).filter(onlyUnique);
var theseTargetModules = theseEdges.map(function (d) {return d.target.module}).filter(onlyUnique);
if (theseSourceModules.length > 1 || theseTargetModules.length > 1) {
node.border = true;
}
else {
node.border = false;
}
});
var modules = nodes.map(function (d) {return d.module})
.filter(onlyUnique)
.map(function (d) {return {id: d, members: []}});
var moduleEdges = [];
var singletons = {id: "singletons", members: []};
var moduleNodeHash = {};
modules.forEach(function (module) {
module.members = nodes.filter(function (d) {return d.module === module.id});
moduleNodeHash[module.id] = module;
if (module.members.length === 1) {
singletons.members.push(module.members[0]);
}
});
modules.push(singletons);
var moduleEdgeHash = {};
edges.forEach(function (edge) {
if (!moduleEdgeHash[moduleNodeHash[edge.source.module].id + "-" + moduleNodeHash[edge.target.module].id]) {
var moduleEdge = {source: moduleNodeHash[edge.source.module], target: moduleNodeHash[edge.target.module], weight: 1};
moduleEdgeHash[moduleNodeHash[edge.source.module].id + "-" + moduleNodeHash[edge.target.module].id] = moduleEdge;
moduleEdges.push(moduleEdge);
}
else {
moduleEdgeHash[moduleNodeHash[edge.source.module].id + "-" + moduleNodeHash[edge.target.module].id].weight += 1;
}
})
return {nodes: modules, edges: moduleEdges}
}
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 modularityGraph = modularityCensus(nodes, edges, result);
var mSVG = d3.select("#viz").append("svg")
.attr("class", "modularity")
.attr("height", 100)
.attr("width", 100)
.style("height", 100)
.style("width", 100)
.style("position", "absolute")
.style("left", 375)
.style("top", 375)
.style("background", "white");
mSVG.selectAll("line")
.data(modularityGraph.edges)
.enter()
.append("line")
.attr("class", "modularity")
.style("stroke-width", function (d) {return d.weight * 2})
.style("stroke", "black");
mSVG.selectAll("circle")
.data(modularityGraph.nodes.filter(function(d) {return d.members.length > 1}))
.enter()
.append("circle")
.attr("class", "modularity")
.attr("r", function (d) {return d.members.length})
.style("stroke", "black")
.style("stroke-width", "1px")
.style("fill", function (d) {return d.id == "singletons" ? "lightgray" : colors(d.id)})
.on("mouseover", moduleOver)
.on("mouseout", moduleOut);
var force = d3.layout.force().nodes(nodes).links(edges)
.size([500,500])
.charge(-300)
.gravity(0.2)
.on("tick", updateNetwork);
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", function (d) {return d.border ? "3px" : "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", function (d) {return d.border ? "3px" : "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 moduleOver(d) {
console.log("MODULE", d);
d3.select(this)
.style("stroke-width", "4px")
d3.select("svg.main").selectAll("circle")
.style("stroke-width", function (p) {return p.module == d.id ? "4px" : "1px"})
}
function moduleOut(d) {
d3.select(this)
.style("stroke-width", "1px")
d3.select("svg.main").selectAll("circle")
.style("stroke-width", "1px")
}
function updateNetwork() {
d3.select("svg.main").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.select("svg.main").selectAll("g.node")
.attr("transform", function (d) {return "translate(" + d.x + "," + d.y + ")"});
d3.select("svg.modularity").selectAll("circle")
.each(function (d) {
var theseNodes = d.members;
var avgX = d3.mean(theseNodes, function (p) {return p.x});
var avgY = d3.mean(theseNodes, function (p) {return p.y});
d.x = avgX / 5;
d.y = avgY / 5;
})
.attr("transform", function (d) {return "translate(" + d.x + "," + d.y + ")"});
d3.select("svg.modularity").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});
}
function updateModularityNetwork() {
}
}
</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