Best layout algorithm for large graph with disconnected components

Usage
1

Hi everybody, I have a graph with approx. 15k vertices which will have a couple of very large components where are to find most of the vertices, and then all others won’t be very connected. I have some difficulties in finding the proper layout to get a decent plot, even the algorithms for large graph don’t produce a satisfactory result.
Any suggestions?

Thanks a lot.

(Btw, I also have a .txt with all edges to be passed in add_edges, is there a way I can upload them here somewhere?)

2

@Matteo I enabled uploading .txt files. Please go ahead. If it’s large, please zip it first.

Happy Easter! :rabbit: :egg:

3

@tamas Is the layout_merge_dla function exposed in python-igraph? If it is not, and if it works well, perhaps it should be. Some large-graph-oriented layouts, such as DrL, do not tolerate non-connected graphs.

P.S. I have not actually used this layout meging method myself, so I am not sure if it works well or not.

4

Thanks a lot! Unfortunately I am not allowed to upload files (I am a new user…)

5

Please try attaching it again.

6

Thanks a lot, here is my .txt!!
upload.txt (210.7 KB)

7

Hmmmm, I don’t think it’s exposed in python-igraph. (To be honest, I’m not even sure what it does, it was added by Gábor a long time ago).

I think that instead of exposing this function, maybe the layout merging should be completely transparent to the user. In other words, if we know that a certain layout algorithm does not handle disconnected graphs, we should let igraph lay out the graph one component at a time, and then we would need to merge these layouts nicely instead of asking the user to call layout_merge_dla() or any other layout merging function separately. (Even for layout algorithms that can cope with disconnected graphs, like igraph_layout_circle(), it still makes sense to decompose the graph first and lay out the components one by one).

8

Mathematica does exactly that: most layouts are done per-component, then merged. There are multiple different merging methods. There is a reasonable default and this can be adjusted.

However, some layouts do not work per-component, as this would be counter-productive. Notably, the circular layout is not done per-component.

@tamas If you want to improve this in python-igraph, you should definitely take a look at Mathematica’s system, as it is very well designed. You can use it as inspiration, take the best parts, fix the few bad ones. We can even have a Skype/Zoom and I show you.

1 Like