Libove Blog

Personal Blog about anything - mostly programming, cooking and random thoughts

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.

Picture of notes about spring models

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:

Picture of the florentine families graph