# 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.

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:

30F45

Keywords: