Theory

Clustering and Reeb graph

The mapper algorithm was introduced by Singh-Mémoli-Carlsson in 2007.

Recall the dendrogram (clustering) algorithm:

Given a fixed $\epsilon >0$, two points $x,y$ are considered equivalent if there is a sequence of points

$$x=x_0,x_1,x_2,\dots ,x_k=y$$

and the distance between successive points is much less than $\epsilon$.

Now consider connected components (“clusters”) for each fixed $\epsilon$. The clustering algorithm computes this and the calculation is essential the same as persistent homology $H_k$ for $k=0$.

Reeb graph

Given a Morse function $f:M\to \mathbb{R}$ on a manifold $M$, the Reeb graph is formed by the equivalence relation:

Two points $x,y\in M$ are equivalent if:

• $f(x)=f(y)$ AND
• $x,y$ are in the same connected component of $f^{-1}(f(x))$

Mapper algorithm

Let us be given:

• A finite metric space $(X,d)$
  • I.e. a finite collection of points $\{x_1,x_2,\dots ,x_k\}$ with distances between them; usually $X\subset {\mathbb{R}}^n$
• A “filter function” $f:X\to {\mathbb{R}}^n$
• A finite cover $\mathcal{C}=\{C_{\alpha }{\}}_{\alpha \in A}$ of $f(X)$ in ${\mathbb{R}}^n$
  • Typically a collection of boxes in ${\mathbb{R}}^n$

Proceed as follows:

(1) Consider the clustering of each $f^{-1}(U_{\alpha })$:

• Choose $\epsilon >0$ and consider clusters at this scale $\epsilon$.
• Write $C_{\alpha ,i}$ for the clusters, so $f^{-1}(U_{\alpha })={⨆}_i{C}_{\alpha ,i}$

(2) Form a discrete version of the Reeb graph:

• Vertices: clusters $C_{\alpha ,i}$
• Edges: when $C_{\alpha ,i}$ and $C_{\beta ,j}$ overlap
• Color the vertices according to values of $f$ (on average):

Illustration - Mapper figures from the literature

(Rabadan-Blumberg 2020)

(Nikolau-Levine 2011)