These are hard problems to solve, even approximately, and nothing we're doing is original. Like quantitative finance, a lot of the original research comes from outside the field (ie. "quasi-clique detection in protein-protein interaction networks"). For those that are interested, there's a lot of information in recent public or easily-available research papers. A weekend spent programming a good idea from a paper is well worth it.
For better or worse, we don't use any graph-specific heuristics beyond general assumptions of the graph's structure (which may or may not be correct, but that's another story...). We're dealing with a massive sparse graph whose vertex set, but not edge set, fits in memory (RAM). Embarrassingly, the edges are stored in a database in MySQL; we might be running the world's largest graph on MySQL, but I think we get better performance from MySQL than we could from any other products. Needless to say, we're not using anything relational. Like a lot of graphs (the Web, social networks, etc.), the number of edges is several orders of magnitude larger than the size of the vertex set, so we plan accordingly.
Perhaps my use of the term "partition" above is incorrect; these aren't perfect partitions (they don't exist, except in theory), but are what's known as "quasi-cliques" (the field of graph theory is rife with jargon).
We're happy with what we've come up with; contrary to most, the limits we face are mostly due to limited storage capacity rather than limited computation time or network capacity, which is essential for handling growth.
Sorry if all of this has been too general; there's not too much I can say specifically without revealing our "secret sauce". :D