8  Ball mapper

8.1 The Vietoris-Rips complex

Another way to reduce the complexity of a metric space is to approximate it by a simplicial complex. Simplicial complexes are like small building blocks glued together, each of these blocks a small representative of an $n$-dimensional space: points, line segments, triangles, tetrahedrons, and so on.

The Vietoris-Rips complex is build as follows: given a metric space $(X,d)$ and an $ϵ>0$, define the following simplicial complex:

$$VR(X,ϵ)=\{[x_1,\dots ,x_n]d(x_i,x_j)<ϵ,\mathrm{\forall }i,j\}$$

that is: the points of $X$ are our vertices, and we have an $n$-simplex $[x_1,\dots ,x_n]$ whenever the pairwise distance between $x_1,\dots ,x_n$ is less than $ϵ$. This condition is equivalent to ask that

$${\cap }_{i}B(x_i,ϵ)\ne \mathrm{\varnothing }$$

where $B(x,ϵ)$ is the ball of center $x$ and radius $ϵ$.

The black dots are points in a metric space; the pink circles are $ϵ$ balls around the points; in green, we have the Vietoris-Rips complex. Source: https://www.researchgate.net/publication/331739415_Topological_data_analysis_for_the_string_landscape

8.2 The ball mapper

The ball mapper is clearly inspired by the Vietoris-Rips complex. Given a metric space $(X,d)$ with $X=\{x_1,\dots ,x_n\}$, select a subset of indexes $L\subseteq \{1,\dots ,n\}$ and define the ball mapper graph G as follows: the set of vertices of $G$ is $L$, and set of edges $E$ given by

$$(i,j)\in E\iff B(x_i,ϵ)\cap B(x_j,ϵ)\ne \mathrm{\varnothing }$$

The ball mapper then can be seen as the 1-skeleton of the Vietoris-Rips, but create using balls whose center can only be the elements indexed by $L$.

To exemplify, consider a circle

using TDAmapper
import GeometricDatasets as gd

X = gd.sphere(1000, dim = 2);

Check that it is indeed a circle:

using CairoMakie
scatter(X)

Now take $L$ as a hundred random points and let’s create the ball mapper of $X$ with radius $ϵ=0.1$:

L = rand(1:1000, 100)
mp = ball_mapper(X, L, ϵ = 0.5);

mapper_plot(mp)

That’s quite a circle!