Persistent homology of unweighted complex networks via discrete Morse theory

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.

arXiv comment36 pages, 6 main figures, SI Appendix and SI Figures; SI Tables available upon request from authors

References in corpus (19)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Lethality and centrality in protein networks
• Self-similar community structure in organisations
• Hyperbolic Geometry of Complex Networks
• Simplicial models of social contagion
• Persistent Homology of Complex Networks
• Topological strata of weighted complex networks
• Robust network community detection using balanced propagation
• Forman curvature for complex networks
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• The Topology of the Cosmic Web in Terms of Persistent Betti Numbers
• Interdisciplinary and physics challenges of Network Theory
• Emergent Complex Network Geometry
• Weighted Growing Simplicial Complexes
• Beyond the clustering coefficient: A topological analysis of node neighbourhoods in complex networks
• Hyperbolic Graph Generator
• Dense Power-law Networks and Simplicial Complexes

Cited by in corpus (4)

• Is the Observable Universe Consistent with the Cosmological Principle?
• Topological Data Analysis of Human Brain Networks Through Order Statistics
• Forman-Ricci curvature and Persistent homology of unweighted complex networks
• Creating Semiflows on Simplicial Complexes from Combinatorial Vector Fields