A fine-grained distance metric for analyzing Internet topology

One of the defining properties of small worlds is the prevalence of short paths connecting node pairs. Unfortunately, as a result the usual notion of distance is not particularly helpful in distinguishing neighborhoods in such graphs. This is the case, for example, when analyzing the interdomain routing system of the Internet. We describe a motivating problem that requires a finer-grained notion of distance. The problem is quite simple to state: how can any given network operator in the Internet determine which paths pass through its network? Surprisingly, the nature of Internet routing makes this question rather hard to answer. To address this problem, we define a new distance metric on graph nodes. This metric has useful and interesting properties: it is easy to compute and understand, it can be used to sharply distinguish neighborhoods in networks, and it remains useful even in small-world networks. We show how we use this metric to address our motivating problem, and more generally how it can be used for visualization and dimensionality reduction of complex networks.