[zoudini]

In practice though, is the degree of connectedness really ever that high? I was under the impression that many real world phenomena (from social networks to biological interaction networks) exhibit small-world phenomena and you tend to get more well-connected subgraphs that are connected by important hub nodes. So it would seem to me like applying some careful heuristics (and keeping track of important bottlenecks/hubs) would still allow you to do computations in chunks.

Would love an expert on the subject to chime in.

[jbooth]

It's not, a lot of the time, but in order to take advantage of that you generally need some domain-specific hack. More general solutions generally assume the possibility of interconnectedness at any point, ie, you can't rule it out, which means you'll need some kind of fast internode lookup mechanism as mentioned by pjscott.