Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs
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.
Code (3)
Tasks
ClusteringTopological Data AnalysisSimilar Papers 제목 키워드 기반
Skeletonization and Reconstruction based on Graph Morphological Transformations
Multiscale shape skeletonization on pixel adjacency graphs is an advanced intriguing research subject in the field of image processing, computer vision and data mining. The previous works in this area almost focused on t…
Open-Ended Question AnsweringSkelite: Compact Neural Networks for Efficient Iterative Skeletonization
Skeletonization extracts thin representations from images that compactly encode their geometry and topology. These representations have become an important topological prior for preserving connectivity in curvilinear str…
BenchmarkingComputational EfficiencyA skeletonization algorithm for gradient-based optimization
The skeleton of a digital image is a compact representation of its topology, geometry, and scale. It has utility in many computer vision applications, such as image description, segmentation, and registration. However, s…
BenchmarkingDeep LearningImage DescriptionTopology preserving thinning for cell complexes
A topology preserving skeleton is a synthetic representation of an object that retains its topology and many of its significant morphological properties. The process of obtaining the skeleton, referred to as skeletonizat…
Curve Skeletonization in Continuous domain for Meshes and Point Clouds
Advancements in 3D curve skeletonization are accelerating progress across a wide range of applications. However, developing robust skeletonization algorithms that capture intricate object details remains challenging. Ske…
Point Clouds