Kamada-Kawai for networks with 10^5 + nodes.

[Ben Griffin]

I have been using the Kamada-Kawai algorithm within networkx and have found it really good for my purposes, but I have come to a cul-de-sac.

The set of network I am looking at are very regular - the nodes and edges are counted  (in 3 dimensions - normalised across the surface of a unit sphere) as follows.

The nodes are initialised with a good approximation of their final positions (no edges cross) but the algorithm does a great job for improving that layout.

given network G(n)

Let k = 4*9^(n+1)

G has k+1 nodes and 3k+1 edges

n  nodes edges

--------------------------------

0, 36+1,  108+1

1, 324+1,  972+1 

2, 2916+1, 8748+1

3, 26244+1, 78732+1

--------------------------------

4, 236196+1, 708588+1

5, 2125764+1, 6377292+1

6, 19131876+1,  57395628+1

--------------------------------

networkx (on my computer) is failing at n > 3 (eg 236,197/708,589 nodes/edges) due to memory issues.

I am hoping that I can find a means of using the algorithm for n = 6 (or even higher).

I only need to store the final positions of those nodes.

I see that the main processing is being done by SciPy optimize.minimize

Along with a cost function that uses numpy einsum, along with some normalisation and so on.

Can anyone recommend a means of solving the K-K algorithm using networks of this scale?

[Dan Schult]

Kamada-Kawai uses an optimization that requires all-to-all distance calculations -- so it creates dense matrices that grow in memory usage like N^2 for N nodes and aren't able to use sparse representations. I have tried different scipy.optimize methods but they don't improve the memory usage because of this same N^2 dependence. And maybe there are other minimization libraries that would be helpful, but I suspect it is fundamental issue with this approach.

You could try a different layout function like `nx.spring_layout(G, pos=pos)` which is better from a memory perspective. 

And there may be others that work well for your case. (Since your networks are very regular, perhaps there is a formula for where to put the nodes, but I guess you already have that to create your starting positions.)  I've heard of other approaches which involve splitting the network into parts, but they are very network-symmetry dependent, and don't work as well for updating close-but-not-quite positions. It doesn't sound like your case fits that approach either.

It'd be great to hear from folks who have thought about this. And if you (Ben) find an approach that works better put a note in a new issue on github so we track it.

Best,

Dan