Ask HN: What is the best software to visualize a graph with a billion nodes?

Post by hasmanean » Fri, Aug 02, 2024, 1:24 PM UTC

heresie-dabord wrote: post #32

shoo wrote: post #5

what decision / downstream process is going to consume the 1B node graph render? is producing a render really necessary for that decision, or is rendering the graph waste? is there a way you can subsample or simplify or approximate the graph that'd be good enough? in some domains, certain problems that are defined on graphs can be simplified by pre-processing the graph, to reduce the problem to a simpler problem. e.g…

> is producing a render really necessary for that decision, or is rendering the graph waste? Just to be clear, the OP already has a graph . There are nodes and relationships. The graph can be queried for understanding. Rendering the graph is tractable for a small graph or a portion of the graph. Trying to render all the nodes in an enormous graph is almost always an expensive quixotic adventure.

Post by infecto » Fri, Aug 02, 2024, 1:25 PM UTC

CuriouslyC wrote: post #21

You don't. generate a hierarchical clustering of the data, then collapse nodes into groups to get under a data set size threshold at any given view distance. That gives you full interaction and the ability to do mouseover info on groups, while being able to zoom in and interact with individual nodes if you want.

Post by neomantra » Fri, Aug 02, 2024, 1:35 PM UTC

viraptor wrote: post #16

It really feels like an under defined task. Do you actually need to see those nodes? At that scale, you never want to render 100B of them. Instead you would need some kind of density aggregation when zoomed out and moving to LoD style k-d tree partitioning when zoomed in. That's almost the area of rendering engines like Unreal's Nanite. You can create your own renderer for data like this, but game engines are likely…

Post by michaelt » Fri, Aug 02, 2024, 2:01 PM UTC

vbrandl wrote: post #45

michaelt wrote: post #37

You can visualise a graph with 9 billion nodes on https://www.openstreetmap.org :) You could copy their design, if you know how you want to project your nodes into 2D. Essentially dividing the visualisation into a very large number of tiles, generated at 18 different zoom levels, then the 'slippy map' viewer loads the tiles corresponding to the chosen field of view. Then a PostGIS database alongside, letting you run…

I would guess OSM uses optimizations for eucledian graphs, where the path a->c is always shorter than a->b->c. This restriction makes e.g. TSP solvable. But this property does not hold for any generic graph. I don't know if this makes visualisation also easier.

Post by aeonik » Fri, Aug 02, 2024, 2:20 PM UTC

infecto wrote: post #44

CuriouslyC wrote: post #21

You don't. generate a hierarchical clustering of the data, then collapse nodes into groups to get under a data set size threshold at any given view distance. That gives you full interaction and the ability to do mouseover info on groups, while being able to zoom in and interact with individual nodes if you want.

This is the way imo. Nobody is consuming 100b nodes in a chart.