Skip to content

Instantly share code, notes, and snippets.

@gouldingken

gouldingken/coarseClusters.js

Created May 25, 2016 16:49
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 gouldingken/9b666ff74bc078d9a70c976def10f94f to your computer and use it in GitHub Desktop.
Save gouldingken/9b666ff74bc078d9a70c976def10f94f to your computer and use it in GitHub Desktop.
Download ZIP
Simpler way to handle hierarchical clusters in ngraph.louvain
Raw
coarseClusters.js
var modularity = require('../../');//require('ngraph.louvain');
var coarsen = require('ngraph.coarsen');
module.exports = function (graph, maxDepth) {
var clusters = modularity(graph);
var clustersByLevel = [];
maxDepth = maxDepth || 5;
var getNodesByCluster = function (graph, clusters) {
var byCluster = {};
var nodeCnt = 0;
graph.forEachNode(function (node) {
var cls = clusters.getClass(node.id);
if (!byCluster[cls]) byCluster[cls] = [];
byCluster[cls].push(node.id);
nodeCnt++;
});
clustersByLevel.push(byCluster);
};
var clusterAgain = function (clusters) {
graph = coarsen(graph, clusters);
clusters = modularity(graph);
getNodesByCluster(graph, clusters);
return clusters;
};
var depth = 0;
getNodesByCluster(graph, clusters);
while (clusters.canCoarse() && depth++ < (maxDepth - 1)) {
clusters = clusterAgain(clusters);
}
var clusterIdsByNode = {};
var explode = function (level, cid, parentIds) {
var arr = clustersByLevel[level][cid];
if (level === 0) {
arr.forEach(function (nodeId, i) {
clusterIdsByNode[nodeId] = parentIds;
});
} else {
arr.forEach(function (nextId, i) {
var pids = parentIds.slice(0);//clone
pids.push(nextId);
explode(level - 1, nextId, pids);
});
}
};
Object.keys(clustersByLevel[clustersByLevel.length - 1]).forEach(function (cid) {
explode(clustersByLevel.length - 1, cid, [cid]);
});
return {
getClass: function (nodeId) {
if (!clusterIdsByNode[nodeId]) return null;
return clusterIdsByNode[nodeId][0];
}
};
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment