Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Python library for embedding large graphs (Written in Rust)

github.com

Post reply on HN
Print view View original

21–26 of 26 posts

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#21

Post by bArray »

h4kor wrote: post #5
sean_pedersen wrote: post #2

A lib generating 2D artifacts might benefit from showcasing these artifacts using image technology for the curious minds.

Thanks for the feedback. The library only calculates the positions and has no graphical output. As an example: I created this to build this embedding of Mastodon instances. https://h4kor.github.io/fediverse-explorer/

Could you not give input and output examples for the graphs? I.e. show networkx before and after your positioning?

Also how well will this scale for large numbers of nodes, say thousands? Currently using networkx I have to perform tens of thousands of iterations on the spring_layout to get quite mediocre results.

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#22

Post by GraphLover9000 »

Have you considered just writing a Rust library and also releasing a thin Python wrapper over it as a separate project? That way, other people could write their own thin wrappers in their high level languages of choice and use your fast implementation via FFI.

I have spent some time looking into graph drawing algorithms and it seems to me that writing a good, optimised algorithm is non-trivial!

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#23

Post by h4kor »

bArray wrote: post #21
h4kor wrote: post #5

Earlier quoted context omitted.

Thanks for the feedback. The library only calculates the positions and has no graphical output. As an example: I created this to build this embedding of Mastodon instances. https://h4kor.github.io/fediverse-explorer/

Could you not give input and output examples for the graphs? I.e. show networkx before and after your positioning? Also how well will this scale for large numbers of nodes, say thousands? Currently using networkx I have to perform tens of thousands of iterations on the spring_layout to get quite mediocre results.

I've two models implement, one of which is the networkx model, which I would recommend at the moment.

I implemented this because networkx was to memory consuming and too slow.

Where networkx crashed with 24k nodes I was able to embed them with this library, it will still take several hours, but at least it's doable. The number of iterations should be on same magnitude as the number of nodes. For my graph #Iteration = 1/2 #nodes was sufficient.

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#24

Post by h4kor »

lmeyerov wrote: post #11

I'm curious what makes it for embedding large graphs - afaict the core is a spring model implemented as O(n^2) in nodes and single-threaded? Wasn't sure of the _size param for the nested loop, maybe I'm misreading. Was hoping there'd be something fun to solve the asymptotic scaling limit via fast multipole, NN's, etc :)

Main benefit over alternative (e.g. networkx): Use all cores of your machine + lower memory footprint. I had problems working with a 24k node graph, which is why I created this library.

For speed I want to try two things in the future: Barnes–Hut simulation and doing the computation on the GPU.

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#25

Post by h4kor »

anentropic wrote: post #19
h4kor wrote: post #5

Earlier quoted context omitted.

Thanks for the feedback. The library only calculates the positions and has no graphical output. As an example: I created this to build this embedding of Mastodon instances. https://h4kor.github.io/fediverse-explorer/

I did also want to see a picture, presumably the point of the lib is to make a nice layout of nodes even though that then has to be rendered with another tool?

Yes, I built it as a replacement for the networkx spring_layout function.

Re: Show HN: Python library for embedding large graphs (Written in Rust)

#26

Post by lmeyerov »

h4kor wrote: post #24
lmeyerov wrote: post #11

I'm curious what makes it for embedding large graphs - afaict the core is a spring model implemented as O(n^2) in nodes and single-threaded? Wasn't sure of the _size param for the nested loop, maybe I'm misreading. Was hoping there'd be something fun to solve the asymptotic scaling limit via fast multipole, NN's, etc :)

Main benefit over alternative (e.g. networkx): Use all cores of your machine + lower memory footprint. I had problems working with a 24k node graph, which is why I created this library. For speed I want to try two things in the future: Barnes–Hut simulation and doing the computation on the GPU.

Ah yeah, I'd still fix the asymptotics first before doing multicore: 10X multicore speedup on a problem means little when haven't done the 100X+ speedup :) we do 500k+ node graphs on frontend, and million/billion on backend.. but after the core is sane
Post reply on HN