License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.25
URN: urn:nbn:de:0030-drops-59175
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5917/
Go to the corresponding LIPIcs Volume Portal

Carrière, Mathieu ; Oudot, Steve

Structure and Stability of the 1-Dimensional Mapper

pdf-format:
LIPIcs-SoCG-2016-25.pdf (0.6 MB)

Abstract

Given a continuous function f:X->R and a cover I of its image by intervals, the Mapper is the nerve of a refinement of the pullback cover f^{-1}(I). Despite its success in applications, little is known about the structure and stability of this construction from a theoretical point of view. As a pixelized version of the Reeb graph of f, it is expected to capture a subset of its features (branches, holes), depending on how the interval cover is positioned with respect to the critical values of the function. Its stability should also depend on this positioning. We propose a theoretical framework relating the structure of the Mapper to that of the Reeb graph, making it possible to predict which features will be present and which will be absent in the Mapper given the function and the cover, and for each feature, to quantify its degree of (in-)stability. Using this framework, we can derive guarantees on the structure of the Mapper, on its stability, and on its convergence to the Reeb graph as the granularity of the cover I goes to zero.

BibTeX - Entry

@InProceedings{carrire_et_al:LIPIcs:2016:5917,
  author =	{Mathieu Carri{\`e}re and Steve Oudot},
  title =	{{Structure and Stability of the 1-Dimensional Mapper}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5917},
  URN =		{urn:nbn:de:0030-drops-59175},
  doi =		{10.4230/LIPIcs.SoCG.2016.25},
  annote =	{Keywords: Mapper, Reeb Graph, Extended Persistence, Topological Data Analysis}
}

Keywords: Mapper, Reeb Graph, Extended Persistence, Topological Data Analysis
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI