I have a graph of several thousand nodes and edges and I notice that the performance of Cytoscape.js with force-directed JavaScript layout algorithms (cose and cola) is lacking.
I wonder if I should invest time to look for other libraries or algorithms or if the complexity of those algorithms is too high in general. In a naive algorithm, I guess that every node has to be compared to every other one, so there should be a quadratic complexity, but with clever filtering on data with low connectivity I could imagine good approximations (I don't need mathematically perfect results, just something intuitive for the users).
My goal is to layout a graph in under 10 seconds on a typical user machine.
Publications I found (Google Scholar for "force directed complexity"):
- A fast adaptive layout algorithm for undirected graphs (1995) estimates O(|V|^3)
- The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings says it's difficult to compute precisely (?, I'm not a graph theorist)
- A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs "produces drawings in two, three, and higher dimensions in sub-quadratic time and space", I will try to find a JavaScript implementation of that one.
For the layout algorithm that uses attractive forces between adjacent nodes and repulsive forces between all nodes, you could use a Barnes--Hut style approximation for the repulsive forces that result from faraway nodes. Only a brief sketch here because B--H is a common school assignment, and there should be plenty of tutorial materials on it. The basic idea is, at each step, perform a recursive quad-tree dissection of the input nodes, counting the number of nodes in each subdivision. Then, to approximate the force on a particular node, traverse the tree recursively. If we arrive at a subdivision that is far from that node, then calculate the repulsive force as if every node in the subdivision lies at the center (or precompute the mean, whatever seems to work).