Topological Strata of Weighted Complex Networks

Giovanni Petri, Martina Scolamiero, Irene Donato, Francesco VaccarinoPLoS 2013 · DOI

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:

  1. Filtration: Instead of picking one threshold, edges are ranked from strongest to weakest and added to the network one by one.
  2. 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.
  3. 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.
The Weight Rank Clique Filtration process (a) and its application to identifying topological holes in the US Air network (b) and generic clusters (c).

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

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.
BibTeX
@inproceedings{petri2013topological,
  author = {Giovanni Petri and Martina Scolamiero and Irene Donato and Francesco Vaccarino},
  title = {{Topological Strata of Weighted Complex Networks}},
  booktitle = {PLoS},
  year = {2013},
  doi = {10.1371/journal.pone.0066506},
}
Figure