Building a Spring Graph Layout Algorithm in Rust

After scraping "all" Mastodon instances, I wanted to visualize the graph of instances. My expectation is that this is a (quiet dense) social graph. To bring order in such a graph a Force-directed graph model can be used. I previously used the networkx implementation for this. However the peers graph I currently have is too large, with 24007 nodes and over 80 million edges. When trying to import this into networkx I simply run out of memory (16GB). After asking for advise on Mastodon, I tried out gephi, which also ran out of memory before loading the entire graph.

Because I still want to visualize this graph, I've decided to write my on graph layouting program. For the first implementation I followed the slides of a lecture at KIT. This gave me some janky but promising results, as I was able to load my graph and an iteration only required ~10 seconds. To validate my implementation I created a debug graph, consisting of 2000 nodes with 4 clusters of different sizes.

After this first implementation I took pen and paper and thought about the problem a bit. This lead to an improved version, with a simpler model leading to faster execution times and quicker convergence.

Embedding the mastodon instances graph, is still challenging. The algorithm creates oscillation in the graph, which I suspect are introduced by one (or multiple) large cliques. I will post an update soon.

Update:

Bonus image of the florentine families graph: