Here are a few references that solve problems on very large graphs: [1] implements work-efficient parallel algorithms for a list of fundamental graph problems.

Here are a few references that solve problems on very large graphs: [1] implements work-efficient parallel algorithms for a list of fundamental graph problems. They report times on a O(200B) edge graph on a single multicore. [2] reports distributed running times for BFS, connectivity, PageRank, and SSSP on a large number of distributed hosts. The times are usually slower than the single-machine times, despite using two orders of magnitude more threads. [3] Reports connectivity times on a truly large graph that is not publicly available (several trillions of edges). My feeling is that unless you are at FAANG or a big national lab, the largest graphs that will show up in practice (today) are on the order of billions of edges, and can be solved quickly using single-machine multicores. [1] https://arxiv.org/abs/1805.05208 https://arxiv.org/abs/1805.05208 [2] https://www.cs.utexas.edu/~roshan/Gluon.pdf https://www.cs.utexas.edu/~roshan/Gluon.pdf [3] https://arxiv.org/abs/1807.10727 https://arxiv.org/abs/1807.10727