> 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.