Abstract
The statistical mechanical approach to complex networks is the dominant paradigm in describing natural and societal complex systems. The study of network properties, and their implications on dynamical processes, mostly focus on locally defined quantities of nodes and edges, such as node degrees, edge weights and -more recently- correlations between neighboring nodes. However, statistical methods quickly become cumbersome when dealing with many-body properties and do not capture the precise mesoscopic structure of complex networks. Here we introduce a novel method, based on persistent homology, to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, which are invisible to existing methods. Their properties divide weighted networks in two broad classes: one is characterized by small hierarchically nested holes, while the second displays larger and longer living inhomogeneities. These classes cannot be reduced to known local or quasilocal network properties, because of the intrinsic non-locality of homological properties, and thus yield a new classification built on high order coordination patterns. Our results show that topology can provide novel insights relevant for many-body interactions in social and spatial networks. Moreover, this new method creates the first bridge between network theory and algebraic topology, which will allow to import the toolset of algebraic methods to complex systems.
Introduction
Most network analysis relies on local properties, such as node degree or edge weight. While useful, these metrics often fail to capture the "many-body" or non-local structure of a network—the mesoscopic fabric of the system. In weighted networks, researchers typically select an arbitrary threshold to prune weak links, a process that often destroys vital structural information.
This paper introduces a novel framework using persistent homology to map the organization of weighted networks across all weight scales simultaneously. By tracking the "holes" in connectivity—regions of weak connectivity surrounded by strong loops—researchers can identify global characteristics that traditional local metrics completely miss.
Methodology: Weight Rank Clique Filtration
The authors introduce the Weight Rank Clique Filtration (WRCF) method to detect these non-local structures:
- Filtration: Instead of picking one threshold, edges are ranked from strongest to weakest and added to the network one by one.
- Clique Complexes: As edges are added, the system builds a "clique complex." For example, three mutually connected nodes form a 2D triangle (a 2-clique); four nodes form a 3D tetrahedron.
- Persistent Homology: The method tracks the "birth" and "death" of topological holes. A hole is born when a loop of strong edges forms and "dies" when the area inside the loop is filled in by subsequent edges forming cliques.
Key Insights: The Two-Class Taxonomy
By validating this method across diverse datasets—including gene interactions, neural networks, airport infrastructures, and social media—the study identifies two broad categories of networks based on their "hollowness":
- Class I (e.g., Gene networks, US Air network): Characterized by small, hierarchically nested holes. These networks are topologically "solid" and organized; their structure is often driven by underlying geometry or functional constraints.
- Class II (e.g., Twitter, Co-authorship): These display larger, longer-lived holes and look much more like their randomized counterparts.
Topology Dictates Dynamics
A significant finding is the link between a network's holes and its spectral properties. Class I networks have much larger Laplacian spectral gaps, meaning their topological structure makes them significantly harder to synchronize than Class II networks. This provides a topological explanation for why certain systems are more resistant to global synchronization, a property that is invisible to standard tools like degree distributions or clustering coefficients.
Limitations and Future Work
While powerful, finding all maximal cliques is an NP-hard problem, making scaling to massive networks a challenge. Future research aims to adapt this framework for directed networks and explore "multi-persistent homology" to track how these topological strata evolve over time in dynamic systems.
Summary updated