Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs
This addresses visualization challenges for moderately sized graphs in fields like social networks or biology, but it is incremental as it adapts an existing topological tool to graphs.
The paper tackles the problem of visual clutter in node-link diagrams for graphs by proposing a homology-preserving multi-scale skeletonization method using a variation of the mapper construction, resulting in a software tool that enables interactive exploration and demonstrates effectiveness on synthetic and real-world data.
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 {\mog}, 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.