You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Chinese Whispers
graph clustering for ngraph. The algorithm
is known for its speed (time-linear in the number of edges) and works best for
large graphs.
I got algorithm converged for a graph with 200,000 nodes 500,000 edges after
8 iterations. Undirected graph with 2.2 million nodes, 4.5 million edges
converged after 47 iterations.
You can play with small graph (254 edges, 77 nodes) here.
It should converge after 2 iterations.
usage
varcreateWhisper=require('ngraph.cw');// Graph is intance of ngraph.graphvarwhisper=createWhisper(graph);// The algorithm is iterative. We should continue running it until change// rate within clusters is large:varrequiredChangeRate=0;// 0 is complete convergencewhile(whisper.getChangeRate()>requiredChangeRate){whisper.step();}// When change rate is 0 (or very close to 0) we are done.// Now we can query "class" of each node:graph.forEachNode(printClass);functionprintClass(node){console.log(nodeId+' belongs to '+whisper.getClass(node.id));}
By default ngraph.cw treats graph as undirected. You can change this via
optional kind argument:
varcreateWhisper=require('ngraph.cw');// Consider only neighbours with incoming edges:varinDegreeWhisper=createWhisper(graph,'in');// Or outgoing edges:varoutDegreeWhisper=createWhisper(graph,'out');
Iterating over clusters
So far we learned how to get class (or cluster) of every single node. ngraph.cw
allows to do reverse operation too. This example shows how to iterate
over each cluster and see nodes within:
varcreateWhisper=require('ngraph.cw');varwhisper=createWhisper(graph);// assume we've done several iterations:while(whisper.getChangeRate()>0){whisper.step();}// clusters is a Set objectvarclusters=whisper.createClusterMap();clusters.forEach(visitCluster);functionvisitCluster(clusterNodes,clusterClass){// each cluster has class identifier:assert(typeofclusterClass!==undefined);// And list of nodes within cluster:assert(Array.isArray(clusterNodes));}