A Fine-Grained Distance Metric for Small Worlds

Wednesday, February 29, 2012 - 4:00pm - 4:45pm
Keller 3-180
Mark Crovella (Boston University)
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.

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.
MSC Code: