Source-linked AI summary
Topological strata of weighted complex networks
Giovanni Petri, Martina Scolamiero, Irene Donato, Francesco Vaccarino
TL;DR
The paper addresses the limited ability of local or quasilocal network measures to characterize many-body and mesoscopic structure in weighted networks. It introduces a persistent-homology method that tracks weighted holes across a rank filtration. The resulting homological features distinguish two broad network classes and provide topology-based information about higher-order organization.
Problem
Local and quasilocal network measures do not systematically capture many-body or precise mesoscopic structure in weighted networks.
Method
The method rank-orders edge weights, builds a clique filtration of thresholded graphs, and tracks weighted network holes through their birth, persistence, and length.
Results
Weighted-hole properties distinguish Class I networks with small hierarchically nested cycles from Class II networks with larger, longer-lived inhomogeneities.
Takeaways & Limitations
Topology supplies a classification based on high-order coordination patterns and offers insights into many-body interactions in social and spatial networks.
Takeaways & Limitations
The taxonomy is not binary: networks can interpolate between the two classes, and local degree, weight, and correlation measures do not directly explain the distinction.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses the difficulty of extracting significant structure from dense weighted networks without losing information through thresholding. It introduces a rank-ordered filtration and tracks weighted network holes across thresholds using persistent-homology concepts.
- Dense weighted networks contain redundant links whose weights and node degrees span multiple orders of magnitude, obscuring significant structure.Thresholding can simplify these networks but inevitably loses properties of the original graph.
- The method considers all thresholded networks ordered by descending edge-weight threshold rather than selecting a single cutoff.The discrete parameter ϵt scans the ranked edge sequence, and each step retains links heavier than the current threshold.
- Weighted network holes are loops whose cyclic edges meet a weight threshold while crossing edges are strictly weaker, making them H1 generators of the thresholded clique complex.The method follows these generators as holes appear and close during the filtration.
- Each hole is described by birth index βg, persistence pg = δg − βg, and length λg, which respectively capture its filtration position, lifetime, and number of composing links.The filtration is interpreted like stratigraphy, with edge-weight rank acting as depth.
2 Results
Across social, infrastructural, biological, and artificial networks, persistent-homology analysis distinguishes two homological classes whose differences are not captured by local network statistics. These classes also differ in spectral properties and synchronization implications.
- Network comparison: Networks were compared with weight-reshuffled and edge-swapped randomizations that preserve weight and degree sequences while disrupting different correlations.Weight reshuffling destroys weight correlations; edge-swapping preserves the weight sequence while changing network structure.
- Homological classes: Class I networks have shorter, earlier, and broader-lived cycles with shorter lengths than their randomized versions, whereas Class II cycles closely resemble random versions.Class I cycles nest hierarchically across filtration scales; Class II networks show late-appearing, short-persistence, long cycles.
- Homological classes: Class I networks are more solid than their randomized versions, while Class II networks more closely resemble randomized instances despite comparable cycle-abundance ratios.The distinction depends on cycle properties rather than the number of cycles.
- Higher-order organization: Real networks retain higher-order H2 coordination that mostly vanishes in randomized instances, while persistent H1 cycles are more readily generated by randomization.The authors interpret this as evidence for higher-order coordination mechanisms in real-world networks.
- Scope of classification: The two classes are extremes of a continuum, and degree, weight, neighborhood-overlap, and assortativity measures do not consistently discriminate them.Networks such as online messages interpolate between the classes, while local and two-body quantities show mixed behavior within groups.
- Spectral consequences: Class I networks have significantly larger adjacency spectral gaps and Laplacian eigenratios than Class II networks, making them hardly synchronizable.The paper connects homological structure with spectral properties and their implications for network dynamics.
3 Conclusions
The method probes organized structure in weighted networks through homology, distinguishing two network classes and linking homological structure with spectral and dynamical properties.
- The method reveals two network classes distinguished by their homological features, reflecting higher-order organization not captured by local or quasilocal approaches.
- The classes differ markedly in spectral-gap distributions and algebraic connectivity, correlating homological structure with different synchronizability thresholds.
- The framework enables study of weighted rich-club geometry beyond aggregate measures and incorporation of homological information into network embeddings.
Methods and Materials
The paper uses persistent homology with a weight rank clique filtration to identify weighted topological structures in networks. The filtration tracks homological features across nested clique complexes formed by progressively thresholded edge weights.
- Network filtration: The method applies persistent homology to the weight rank clique filtration of a weighted network instead of the Rips-Vietoris filtration commonly used for point clouds.A clique complex is built from complete subgraphs, while edge weights determine the filtration sequence.
- Simplicial homology: Simplicial homology constructs chain spaces from faces, with cycles given by kernels of boundary maps and homology groups defined as cycles modulo boundaries.The boundary maps satisfy ∂n−1 ◦ ∂n = 0, implying every boundary is a cycle.
- Persistent homology: Persistent homology studies homology across an increasing sequence of simplicial complexes rather than a single complex.The induced homology maps need not be injective, so features may disappear along the filtration.
- Network filtration: The filtration ranks link weights from highest to lowest, thresholds the graph at each ranked value, and constructs the corresponding clique complex.These clique complexes are nested as the threshold sequence progresses, forming the weight rank clique filtration.
- Interpretation: Persistent one-dimensional cycles represent weighted loops whose internal links are relatively weaker than the links establishing the surrounding clique structure.This interpretation distinguishes weighted-network H1 features from H1 features obtained through a Rips-Vietoris filtration.
Supplementary Information for ”Topological strata of weighted complex networks”
The supplementary material develops persistent homology for weighted networks, defines the relevant simplicial and homological structures, and describes the weight rank clique filtration and its application to network classification.
- Simplicial complexes: A clique complex contains an n-face for every (n + 1)-clique in the underlying graph.The construction satisfies the simplicial compatibility conditions because subsets and intersections of cliques remain cliques.
- Homology: The first Betti number counts two-dimensional polygonal holes, while the zeroth counts connected components.These Betti numbers are ranks of the corresponding homology groups.
- Persistent homology: Persistent homology extends simplicial homology across a filtration of nested complexes, with maps between their homology groups.A filtration is a family X_v with X_v ⊆ X_w whenever v ≤ w.
- Filtrations: The weight rank clique filtration reveals multiscale relations between edge weights and links that a single clique complex cannot determine.This distinguishes the weighted-network filtration from the unweighted clique filtration, whose persistent features are already determined by one clique complex.
- Datasets: The tested networks span social, infrastructural, and biological systems, including a gene-expression network sampled through recursively expanded neighborhoods.The gene network represents genes as nodes and expression correlations, measured by an NIR score, as edges.
- Network classification: The analysis compares persistent H1 generators in real networks with weight-reshuffled and randomized counterparts using persistence, length, and birth-index distributions.The supplementary figures organize these quantities across distribution panels and persistence diagrams.