Persistent homology of unweighted complex networks via discrete Morse theory
30
Citation
63
Reference
10
Related Paper
Citation Trend
Abstract:
Topological data analysis can reveal higher-order structure beyond pairwise connections between vertices in complex networks. We present a new method based on discrete Morse theory to study topological properties of unweighted and undirected networks using persistent homology. Leveraging on the features of discrete Morse theory, our method not only captures the topology of the clique complex of such graphs via the concept of critical simplices, but also achieves close to the theoretical minimum number of critical simplices in several analyzed model and real networks. This leads to a reduced filtration scheme based on the subsequence of the corresponding critical weights, thereby leading to a significant increase in computational efficiency. We have employed our filtration scheme to explore the persistent homology of several model and real-world networks. In particular, we show that our method can detect differences in the higher-order structure of networks, and the corresponding persistence diagrams can be used to distinguish between different model networks. In summary, our method based on discrete Morse theory further increases the applicability of persistent homology to investigate the global topology of complex networks.Keywords:
Persistent Homology
Discrete Morse theory
Computational topology
Topological data analysis
Homology
A central problem in topological data analysis is that of computing the homology of a given simplicial complex. Said complexes can have arbitrary large number of simplices, as can happen, for example, if the space is the Rips-Vietoris or Cech complex of a large data cloud. Thus, pre-processing the simplicial complex to get a smaller complex with the same homology groups and then applying the homology algorithm to the smaller one, has been an active research topic in the last years. In this survey, we discuss some recent papers that examine the complexity of this simplification via Discrete Morse Theory. This survey was prepared as a final project for a course on Computational Topology at The Ohio State University.
Discrete Morse theory
Topological data analysis
Simplicial homology
Persistent Homology
Homology
Computational topology
Simplicial approximation theorem
Cite
Citations (0)
Topological data analysis can reveal higher-order structure beyond pairwise connections between vertices in complex networks. We present a new method based on discrete Morse theory to study topological properties of unweighted and undirected networks using persistent homology. Leveraging on the features of discrete Morse theory, our method not only captures the topology of the clique complex of such graphs via the concept of critical simplices, but also achieves close to the theoretical minimum number of critical simplices in several analyzed model and real networks. This leads to a reduced filtration scheme based on the subsequence of the corresponding critical weights, thereby leading to a significant increase in computational efficiency. We have employed our filtration scheme to explore the persistent homology of several model and real-world networks. In particular, we show that our method can detect differences in the higher-order structure of networks, and the corresponding persistence diagrams can be used to distinguish between different model networks. In summary, our method based on discrete Morse theory further increases the applicability of persistent homology to investigate the global topology of complex networks.
Persistent Homology
Discrete Morse theory
Computational topology
Topological data analysis
Homology
Cite
Citations (30)
The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in $2$-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension $2$.
Persistent Homology
Discrete Morse theory
Topological data analysis
Computational topology
Homology
Bounding overwatch
Cite
Citations (0)
We investigate combinatorial dynamical systems on simplicial complexes considered as {\em finite topological spaces}. Such systems arise in a natural way from sampling dynamics and may be used to reconstruct some features of the dynamics directly from the sample. We study the homological persistence of {\em Morse decompositions} of such systems, an important descriptor of the dynamics, as a tool for validating the reconstruction. Our framework can be viewed as a step toward extending the classical persistence theory to vector cloud data. We present experimental results on two numerical examples.
Persistent Homology
Topological data analysis
Discrete Morse theory
Persistence (discontinuity)
Dynamics
Homology
Cite
Citations (1)
Topological data analysis can extract effective information from higher-dimensional data. Its mathematical basis is persistent homology. The persistent homology can calculate topological features at different spatiotemporal scales of the dataset; that is, establishing the integrated taxonomic relation among points, lines and simplices. Here, the simplicial network composed of all-order simplices in a simplicial complex is essential. Because the sequence of nested simplicial subnetworks can be regarded as a discrete Morse function from the simplicial network to real values, a method based on the concept of critical simplices can be developed by searching all-order spanning trees. Employing this new method, not only the Morse function values with the theoretical minimum number of critical simplices can be obtained, but also the Betti numbers and composition of all-order cavities in the simplicial network can be calculated quickly. Finally, this method is used to analyze some examples and compared with other methods, showing its effectiveness and feasibility.
Discrete Morse theory
Simplicial homology
Persistent Homology
Topological data analysis
Simplicial approximation theorem
Abstract simplicial complex
Homology
Cite
Citations (0)
We develop topologically accurate and compatible definitions for the skeleton and watershed segmentation of a 3D digital object that are computed by a single algorithm. These definitions are based on a discrete gradient vector field derived from a signed distance transform. This gradient vector field is amenable to topological analysis and simplification via For-man's discrete Morse theory and provides a filtration that can be used as input to persistent homology algorithms. Efficient implementations allow us to process large-scale x-ray micro-CT data of rock cores and other materials.
Persistent Homology
Discrete Morse theory
Topological data analysis
Signed distance function
Topological skeleton
Vector flow
Cite
Citations (24)
Among the newer approaches to data analysis are topological methods (TDA), which proved to be effective in analyzing data. In this thesis we analyze data on 911 calls that include a large number of calls. Firstly, we prepare data by grouping calls together using the Vietoris-Rips complex. We do this because it enables us to also analyze smaller areas and connect them. We analyze this complex in two ways: by using Morse theory and persistent homology. Morse theory is used to acquire critical simplices from the complex. They give us new information about the data. Using persistent homology, we produce persistent diagrams that illustrate how homology of a complex changes depending on a parameter. The initiative to use the TDA on such data came from the Department of Sociology at Harvard, where they had already tried to analyze this data by using various mechanical and mathematical models.
Topological data analysis
Persistent Homology
Discrete Morse theory
Homology
Cite
Citations (0)
Topological data analysis can extract effective information from higher-dimensional data. Its mathematical basis is persistent homology. The persistent homology can calculate topological features at different spatiotemporal scales of the dataset, that is, establishing the integrated taxonomic relation among points, lines, and simplices. Here, the simplicial network composed of all-order simplices in a simplicial complex is essential. Because the sequence of nested simplicial subnetworks can be regarded as a discrete Morse function from the simplicial network to real values, a method based on the concept of critical simplices can be developed by searching all-order spanning trees. Employing this new method, not only the Morse function values with the theoretical minimum number of critical simplices can be obtained, but also the Betti numbers and composition of all-order cavities in the simplicial network can be calculated quickly. Finally, this method is used to analyze some examples and compared with other methods, showing its effectiveness and feasibility.
Discrete Morse theory
Persistent Homology
Simplicial homology
Topological data analysis
Simplicial approximation theorem
Homology
Abstract simplicial complex
Cite
Citations (2)
We investigate combinatorial dynamical systems on simplicial complexes considered as {\em finite topological spaces}. Such systems arise in a natural way from sampling dynamics and may be used to reconstruct some features of the dynamics directly from the sample. We study the homological persistence of {\em Morse decompositions} of such systems, an important descriptor of the dynamics, as a tool for validating the reconstruction. Our framework can be viewed as a step toward extending the classical persistence theory to "vector cloud" data. We present experimental results on two numerical examples.
Persistent Homology
Topological data analysis
Discrete Morse theory
Persistence (discontinuity)
Dynamics
Homology
Cite
Citations (0)
The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in $2$-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension $2$.
Persistent Homology
Discrete Morse theory
Topological data analysis
Computational topology
Homology
Bounding overwatch
Cite
Citations (0)