Automatic Graph clustering?

[pathikrit]

http://stackoverflow.com/questions/9490003/web-based-large-scale-graph-drawing-library

[jacomyal]

Interesting feature, indeed. I think it does not have its place in sigma.js core - since it is not directly related to the drawing process, but it would be a really interesting plugin to have. I think it is definitely possible to write a JavaScript implementation of the Louvain method.

[pathikrit]

True. But clustering itself can be pushed to the [visualization part][1]

[1]: http://en.wikipedia.org/wiki/Force-based_algorithms_%28graph_drawing%29

[jacomyal]

You are right, in the way that using a Force-Directed layout algorithm (such as Force Atlas 2 for instance, which is itself already a plugin) is supposed to reveal the clusters. You can also apply a k-means algorithm after the layout, to determine more precisely these clusters.

But I think it would be much faster to separate those processes, since finding the clusters does not have to involve drawing the graph (the most expensive part, in our case).

[jalabiso]

this really interests me as well. I am trying to draw maps of relationships straight out from DB queries, and I'd need to apply layout calculations at some point. Sigma's forceAtlas plugin looks great, but it doesn't really represent clusters in a significative way, instead it positions all nodes around a nice and round circle.

these type of layout (sigmajs.org/examples/parse_data.html) instead are much more significant as the better show clusters. I found these simple sample to be interesting as well: http://mbostock.github.com/d3/ex/force.html

Unfortunately I am not a mathematicians and I wouldn't be able to turn algorithms into usable code myself. could you point me to any code/plugins that could be used 'almost' directly?

[jacomyal]

I am pretty surprised on what you say about ForceAtlas2: The sigma.js ForceAtlas2 plugin and the d3.js example you are talking about are both based on [Force-Directed layout algorithms](http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing).

The ForceAtlas2 example at sigmajs.org is displaying a custom random graph, which is kind of different from real life graphs you could meet in datasets repositories.

I am actually currently looking for a JS library that would be possible to be tweaked to make a sigma.js plugin that computes the clusters, so I hope I will be able to release a plugin in the coming months :)

[BransonGitomeh]

The ForceAtlas2 example at sigmajs.org is displaying a

that link for ForceAtlas2 is broken from my side, how far are you at this?... still coming soon?

[paidge]

I'm very interested by the louvain algorithm as a plugin. I found some examples for D3JS (example1, example2, example3) but I think Sigma is more efficient with big graphs. So I'm searching now for SigmaJS. I just found this link and I'm going to read it :)

[Yomguithereal]

If you are not afraid to try the v2 of the lib which is currently under development, you can also check graphology which has Louvain community detection and which is used by the new version.

[paidge]

which lib are you talking about? SigmaJS v2 ?

[Yomguithereal]

Current version of sigma is v1. If you check the v2 branch you'll see I am working on a totally new version of the library.

[paidge]

Thanks for your response and congratulation for your work ! I finally managed to implement the algorithm to show the web of trust of the first crypto-currency co-created with a really universal basic income. Now I'm working on the layout but I noticed that all customisations are only possible with canvas renderer. I think I have to test the v2 or to wait for the next release.