Network cannot be positioned by the improved layout algorithm - clustering bug

[nicolasvallee]

Hello dear vis contributors,

In LayoutEngine.js one can read the following about the improvedLayout option

 // if there are a lot of nodes, we cluster before we run the algorithm.
 // NOTE: this part fails to find clusters for large scale-free networks, which should
 //       be easily clusterable.
 // TODO: examine why this is so

and I am indeed encountering this issue every time my graph size exceeds the provided clusterThreshold limit (default to 150).

Has there already been some investigation on this? I suspect the performance of vis to be tremendously improved if we are able to fix this, both in performance and the ability fo generate nicely spread out graphs (for example mesh/grid graphs which currently get stuck in a messy folded graph). I am willing to help and wondering if anyone has an idea already, seems like this bug has been here for a long time.

Thanks,

Nico

[nicolasvallee]

For example this 50x50 square mesh grid (2500 nodes, 4900 edges) is stuck in a "local minimum energy" layout : adjacent nodes are indeed adjacent but many "far way" nodes in the graph sense are very close together in the final layout, resulting in a "folded" look of the graph. Using the Kamada Kawai algorithm on a set of clustered nodes for the initial layout could greatly improve the final layout, as the simulation will start on a roughly spread out graph and do the remaining smaller adjustments to unfold everything , if my understanding is correct.

It works fine if I force the algo to not create any clusters by raisingclusterThreshold to the number of nodes of the graph, but the execution time increases a lot. The algorithm should ideally be able to work on clusters.

On this 25x25 mesh grid (625 nodes), the left picture shows a "local minimum energy" layout that is found when not using improved layout. You can see that the graph is folded over itself once and remains stuck in this configuration.
I increased clusterThreshold to 625 to get the picture on the right. Loading is slow but the initial layout seems to do the entire job of positioning the nodes.