Navigability of complex networks

Here's an interesting idea, which falls in the very large set of "things I thought about but have no idea how to implement": M. Boguna, D. Krioukov, kc claffy. Navigability of Complex Networks, arXiv:0709.0303v2. (Published in the November 16, 2008 issue of Nature Physics; I learned about it from physorg.com.) The basic idea is that it is possible to navigate in complex networks by navigating in some underlying hidden metric space. Nodes are close together in the hidden metric space if they are similar to each other in some abstract sense, and they are more likely to be connected to each other in the network if they are closer together.

To take an example where the metric space isn't hidden, one navigates between airports by thinking about distances on the surface of the Earth; if you route greedily, by at each airport taking the flight which gets you closest to where you want to go, you usually will end up at your destination. Of course, this isn't a priori true -- you could get stuck in an infinite loop -- but the point is that real networks seem to obey this.

This is something that I think a lot of people have an intuitive sense of. For example, there are people I've met that when I meet them, I want to ask "why haven't we met before?" -- some combination of shared geography and shared interests makes it seem like we should know each other. (In my own life, there is at least one case of somebody who I never met when I was an undergrad, though there were plenty of amusing stories about mutual friends of ours that we'd both heard; we met shortly after I moved back to Philadelphia for grad school.)