Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs
TL
TL;DR
A variation of the mapper construction targeting weighted, undirected graphs is developed, called mapper on graphs, which generates homology-preserving skeletons of graphs, and how the adjustment of a single parameter enables multi-scale skeletonization of the input graph is shown.
Abstract
Node-link diagrams are a popular method for representing graphs that capture relationships between individuals, businesses, proteins, and telecommunication endpoints. However, node-link diagrams may fail to convey insights regarding graph structures, even for moderately sized data of a few hundred nodes, due to visual clutter. We propose to apply the mapper construction-a popular tool in topological data analysis-to graph visualization, which provides a strong theoretical basis for summarizing the data while preserving their core structures. We develop a variation of the mapper construction targeting weighted, undirected graphs, called mapper on graphs, which generates homology-preserving skeletons of graphs. We further show how the adjustment of a single parameter enables multi-scale skeletonization of the input graph. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.
References112 items
1
Untangling Force-Directed Layouts Using Persistent Homology
2
Adaptive Covers for Mapper Graphs Using Information Criteria
3
Pheno-mapper: an interactive toolbox for the visual exploration of phenomics data
4
Topological Simplifications of Hypergraphs
5