Created
May 25, 2016 16:49
-
-
Save gouldingken/9b666ff74bc078d9a70c976def10f94f to your computer and use it in GitHub Desktop.
Simpler way to handle hierarchical clusters in ngraph.louvain
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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