33 views

Skip to first unread message

Oct 2, 2024, 10:02:49 PMOct 2

to networkx-discuss

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.

**n nodes edges**

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

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

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?

Oct 3, 2024, 9:46:41 AMOct 3

to networkx...@googlegroups.com

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu