I'm working on a side project now that involves encoding all of the links between Wikipedia pages. I've scraped this information to disk, but the memory usage required to encode the structure of this graph is pretty ridiculous - there's millions of nodes and tens of millions of links. While this structure does fit in memory, I'm not sure what I'd do if there were, say, a billion links or a billion pages.

My question is - is there a way of losslessly compressing a graph too large to fit into memory so that it does fit in memory? If not, is there a good lossy algorithm that for some definition of "structure" doesn't lose too much structure from the original graph?