Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 5, 2012

The Spread of a Metric Space

Posted by Simon Willerton

Given a finite metric space XX we can define the spread E 0(X)E_0(X) by

E 0(X) x1 ye d(x,y).E_0(X)\coloneqq \sum_x \frac{1}{\sum_{y} e^{-d(x,y)}}.

This turns out to be a nice measure of the ‘size’ of the metric space. I’ve just finished a paper on this:

In this post I’ll give a quick overview of the paper, mentioning connections to biodiversity; magnitude; volume and total scalar curvature; and Hausdorff dimension.

A few of these ideas are looked at in a slightly more dynamic way in my recent talk at the CRM Exploratory programme on the mathematics of biodiversity: Magnitude and other measures of metric spaces.

I should say that Tom Leinster convinced me to switch to using the word ‘spread’ as prior to that I had been using the much more uncouth word ‘bigness’.

The following five snapshots of the spread are more-or-less independent of each other.

Diversity

The definition of spread was motivated by Tom Leinster and Christina Cobbold’s definition of diversity measures for ecosystems in which they take into account the relative abundances of the species and the relatedness of each pair of species, or in math-speak, we can use these to assign a number to each finite metric space with a probability measure on it – the points represent the species, the metric describes the relatedness and the probability measure describes the relative abundances.

Tom and Christina give us a diversity measure for each number qq with 0q0\le q \le\infty, so for a finite metric space we can use the uniform probabiltiy measure on it and take the diversity measure for q=0q=0: that is precisely the spread.

The more classical version of the Tom and Christina’s measures – the Hill numbers – only takes into account relative abundances of species and not the relatedness of species, so these are defined for probability spaces with no metric on them (or with the discrete metric on them, if you prefer). In that case, the q=0q=0 diversity measure is just the number of species present. So from that point of view, the spread can be seen as an analogue of the number of species in an ecosystem.

Basic behaviour

If XX is a finite metric space with NN points, t>0t \gt 0 and tXt X denotes XX with the metric scaled by a factor of tt then we get the following basic properties of the spread.

  • 1E 0(X)N1\le E_0(X)\le N;
  • E 0(tX)E_0(t X) is increasing in tt;
  • E 0(tX)1E_0(t X)\to 1 as t0t\to 0;
  • E 0(tX)NE_0(t X)\to N as tt\to \infty;
  • E 0(X)e diam(X)E_0(X)\le e^{diam(X)}.

For instance, if tRt R is the following three-point metric space

3 point space

then we get the following plot of the spread as we scale tt.

spread profile

So when the space is scaled very small it looks like there is one point, at medium scales it looks like there are two points, and at large scales all three points are distinctly visible.

Magnitude

Long-time readers of this blog will not be surprised to hear that spread is connected to Tom Leinster’s notion of magnitude (called cardinality in some early blog posts). The magnitude |X||X| of a metric space XX is not always defined; for instance, Tom showed that there is no magnitude defined for a certain scaling of the five-point metric space coming from the complete bipartite graph K 3,2K_{3,2}. If we plot the magnitude of the scalings of this space together with the spread of these scalings then we see that the spread is rather more nicely behaved!

spread profile

Tom Leinster said he thinks this shows that the spread is more suave than the magnitude.

For well-behaved metric spaces the magnitude is an upper bound for the spread – in this case ‘well behaved’ means ‘positive definite’ and such spaces include subspaces of Euclidean space. For homogeneous metric spaces the magnitude and the spread actually coincide.

Dimension

As we have a notion of size, we can associate a notion of dimension.

  • If we scale a line by a factor of tt then its length (its size) scales by a factor of t 1t^1.

  • If we scale a rectangle by a factor of tt then its area (its size) scales by a factor of t 2t^2.

  • If we scale a cuboid by a factor of tt then its volume (its size) scales by a factor of t 3t^3.

Of course, the 11, 22 and 33 appearing there are our usual concept of dimension of those three spaces. So given a notion of size of metric spaces, the associated dimension of a metric space is the growth rate of the size. One has to be precise about what growth rate is here, but you can think of it as the (instantaneous) slope of the log-log plot of size versus scale.

In particular, the spread dimension dim 0(X)dim_0(X) of a metric space XX is defined by

dim 0(X)dlog(E 0(tX))dlog(t)| t=1=tE 0(tX)dE 0(tX)dt| t=1.dim_0(X)\,\coloneqq\, \left.\frac{\mathrm{d} \,log(E_0(t X))}{\mathrm{d} \,log(t)}\right|_{t=1} \, =\, \left.\frac{t}{E_0(t X)}\frac{\mathrm{d}E_0(tX)}{\mathrm{d}t}\right|_{t=1}.

This notion of spread dimension is scale dependent, but that is not unreasonable. Think of a very long and very thin rectangle. If it is scaled very, very small you might think it looks like a point, so is zero-dimensional. As it is scaled up you start to notice its length but not its width, so it seems one-dimensional. As it is scaled even more it finally looks two-dimensional. If this rectangle is actually made from, say, atoms, then if it scaled even more then you start to see the individual points and it begins to look zero-dimensional again.

We can numerically calculate the spread dimension for a rectangle of 1010 by 49004900 points at various scales, and the above describes exactly the kind of phenomena that we see.

dimension profile

If my computer could handle much bigger matrices then I could calculate the dimension profile for say 10001000 by 100000000100000000 points and see a much more pronounced step-like behaviour from zero to one to two to zero dimensions.

We don’t have to stick to boring old shapes like rectangles. We can try fractals! We can take a finite metric space with lots of points which approximates say the Koch curve, get maple to calculate the spread dimension at various scales and plot the result. At medium scales the spread dimension is shockingly close to the Hausdorff dimension of the Koch curve, namely ln4/ln3ln 4/ ln 3. So when it’s not too small and it’s not too large, then the finite approximation looks ‘Koch-like’.

dimension profile

The same phenomemon is seem for finite approximations to Cantor sets and Sierpinski triangles, so there seems to be some geometric content to the spread dimension.

Non-finite metric spaces

There is an obvious way to generalize the notion of spread to a non-finite metric space XX provided that the metric space comes equipped with a canonical measure μ\mu such that the total measure of the space is finite. In that case we just define the spread as follows.

E 0(X) xXdμ(x) yXe d(x,y)dμ(y).E_0(X)\coloneqq\int_{x\in X} \frac{\mathrm{d}\mu(x)}{\int_{y\in X} e^{-d(x,y)} \,\mathrm{d}\mu(y)}.

From that one can calculate the spread of a length \ell straight line segment and of an nn-sphere with radius RR. As it’s getting late, I won’t put the details here, but let the interested reader find out the answers by looking in the paper.

One class of metric spaces with a canonical measure is the class compact Riemannian manifolds. For this class of spaces it is possible to calculate the leading order terms in the asymptotic behaviour of the spread as a space MM is scaled up. These leading order terms depends just on the volume vol(M)vol(M) and the total scalar curvature tsc(M)tsc(M), in particular we have the following.

E 0(tM)=1n!ω n(t nvol(M)+n+16t n2tsc(M)+O(t n4))as t,E_0(t M) = \frac{1}{n!\,\omega_n}\left(t^n vol(M) + \frac{n+1}{6}t^{n-2} tsc(M) +O(t^{n-4})\right) \quad \text{as }\quad t\to\infty,

where ω n\omega_n is the volume of the unit nn-ball.

In particular, for a Riemannian surface Σ\Sigma we have:

E 0(tΣ)=area(Σ)2πt 2+χ(Σ)+O(t 2)as t,E_0(t\Sigma)=\frac{area(\Sigma)}{2\pi}t^2+\chi(\Sigma)+O(t^{-2})\quad \text{as } \quad t\to\infty,

where χ\chi is the Euler characteristic.

Final comments

In conclusion, it seems that this easy to write down measure of size of a metric space has many interesting properties.

Posted at September 5, 2012 5:09 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2553

9 Comments & 1 Trackback

Re: The Spread of a Metric Space

This looks quite neat. I gather from your graphs and examples that the spread has an “intrinsic length scale” of about 1 — in the sense that it considers distinct points to “cohere together” roughly when they are less than distance 1 apart. Is that a correct intuition? Is it possible to write down variants of the spread for which this intrinsic scale is some other number?

Posted by: Mike Shulman on September 5, 2012 10:02 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

There does seem to be a natural length at that kind of scale you mention. I tend think of the units as being centimeters with the metric space being held in my hands, that seems to give a reasonable intuition, but I’ve not got anything much stronger than that to say.

If you change the ee in the definition to another positive constant aa, then natural scale should go from around 11 to around 1/ln(a)1/ln(a).

Posted by: Simon Willerton on September 5, 2012 10:50 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hooray!

Posted by: Tom Leinster on September 6, 2012 1:58 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

I should say that Tom Leinster convinced me to switch to using the word ‘spread’ as prior to that I had been using the much more uncouth word ‘bigness’.

Part of me is really sad that you switched. Would’ve loved ‘bigness’.

Posted by: Todd Trimble on September 6, 2012 6:51 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

‘Bigness’ is a nice word, but I like ‘spread’ better here. This is partly for the boring, pedantic reason that ‘bigness’ sounds too general for any one quantity — why should this be called ‘bigness’ instead of any other quantity? But it’s also because I think what E 0E_0 measures really is how ‘spread out’ the μ\mu-mass of XX is.

Posted by: Mark Meckes on September 6, 2012 3:43 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Figure 3 on page 7 suggests why spread might not be a bad name. The two spaces shown there have the same magnitude, simply because they’re trees with the same number of vertices. (That’s Theorem 4.) But the spread of the spread-out one is greater than that of the clustered-up one.

Posted by: Tom Leinster on September 6, 2012 4:16 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

A minor terminological note: in recent years, “metric measure space” has become a standard term for a metric space equipped with a canonical finite measure.

Posted by: Mark Meckes on September 6, 2012 3:49 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Thanks Mark. Talking of terminological things, Tom said that you’d found the ‘maximum diversity’ in the literature under a somewhat different name. What was it called?

Posted by: Simon Willerton on September 6, 2012 9:31 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Get ready for a mouthful. For a subset AA of NN-dimensional Euclidean space, up to a factor of N!N! times the volume of the unit ball, the maximum diversity of AA is the same as the “Bessel capacity of AA of order (N+1)/2(N+1)/2 and index 22”. Or is that index (N+1)/2(N+1)/2 and order 22? In any case, it’s sometimes denoted B (N+1)/2,2(A)B_{(N+1)/2,2}(A). As far as I can tell, it’s not very well-studied as such —- the main interest seems to be on capacities B α,pB_{\alpha, p} for which αpN\alpha p \le N. When αp\alpha p is bigger than NN, the capacity has some behaviors which seem to be pathological from the point of view of the usual applications of capacities.

Posted by: Mark Meckes on September 7, 2012 1:16 AM | Permalink | Reply to this
Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: April 7, 2013 9:55 PM

Post a New Comment