[chrisweekly]

> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics."

Impressive!

[danbruc]

33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.

[eeks]

It reminds me of that Frank MacSherry paper[1]...

[1] "Scalability! But at what COST?"

[anon7725]

> most existing graph algorithms require the graph to fit into memory.

You can get pretty far with sparse graphs, which are just arrays, in combination with memory mapping.

[ssinchenko]

Agreed, but I didn't see anything like this in popular projects such as Networkit or IGraph. If you have an example of an implementation, I would appreciate it!