Severability of mesoscale components and local time scales in dynamical networks

Yun William Yu, Jean-Charles Delvenne, Sophia N. Yaliraki, Mauricio BarahonaarXiv 2020 · arXiv

Abstract

Identifying functional units in large-scale dynamical networks is a fundamental challenge in complex systems science. This paper introduces "severability," a local quality function designed to identify dynamically coherent clusters—mesoscale components—using only local network information. By balancing the retention of random walkers within a group against their internal mixing rate, severability reveals functional modules across varying time scales. We validate this approach on diverse datasets, including power grids, biological pathways, and image segmentation, demonstrating its scalability and physical interpretability.

Introduction

Modern scientific inquiry is increasingly focused on massive, interconnected systems, from metabolic pathways to global power grids. Traditional analysis often struggles with the "curse of dimensionality" or the lack of global network knowledge. While spectral methods provide mathematical elegance, they often produce global modes that lack physical interpretability. Conversely, standard community detection typically focuses on static topology rather than the dynamic flow of information or energy. There is a critical need for methods that identify "chunks" of a network that function as coherent units over specific time scales.

Methods: The Severability Metric

The authors propose the Severability function, $\sigma(C, t)$, as a local quality metric for a subset of nodes $C$ at a specific "Markov time" $t$. Severability is defined as the average of two competing dynamical properties:

  1. Retention ($\rho$): The probability that a random walker starting within the group remains there until time $t$, measuring the strength of the "barriers" surrounding the component.
  2. Mixing ($\mu$): The degree to which the internal distribution of walkers approaches a steady state, measuring the "smoothness" or lack of internal bottlenecks.

A component is considered highly "severable" if it possesses high barriers to exit and low internal resistance to movement. Mathematically, this is grounded in the Simon-Ando-Fisher theorem, which suggests that such components can be approximated as single "lumped" nodes for long-term dynamical predictions.

Visualizing dynamical landscapes and severability across scales.

To identify these components, a semi-greedy local search algorithm is employed, starting from individual nodes and expanding to find the neighborhood that maximizes severability.

Key Insights: Time as a Microscope

A central contribution of this work is the use of Markov time $t$ as a resolution parameter. At short time scales, only individual nodes appear severable. As $t$ increases, the analytical "lens" zooms out, revealing small clusters, then larger functional modules, and finally the entire network. This hierarchical revelation allows researchers to probe the system at the most relevant scale for their specific problem.

Furthermore, because severability depends only on the out-links of the nodes within the set, it is inherently local. This allows for the discovery of coherent components in "infinite" or partially observed graphs without requiring global computation.

Applications and Results

The utility of severability was demonstrated across several domains:

  • Power Systems: In the IEEE RTS96 test system, collapsing severable components into single variables significantly reduced simulation error compared to arbitrary partitioning methods.
  • Community Detection: On standard LFR benchmarks, severability matched or outperformed state-of-the-art methods like Infomap, particularly in identifying overlapping communities.
  • Image Segmentation: The method successfully segmented cells in noisy fluorescence microscopy images. Notably, the local nature of the algorithm meant that cropping the image did not alter the segmentation of the remaining visible cells.
  • Cognitive Science: In word association networks, severability mapped the conceptual "landscape" around specific terms, identifying overlapping contexts such as "wilderness" and "biology" for the word "nature."

Discussion

Severability offers a robust framework for model reduction and functional analysis in complex networks. By focusing on dynamical coherence rather than just graph topology, it captures the functional essence of network modules. While currently optimized for linear Markovian dynamics, future work aims to extend these theoretical proofs to strongly non-linear or non-Markovian systems. Despite the need for heuristic selection of the optimal Markov time $t$, the method's locality and scalability make it a powerful tool for the analysis of modern Big Data networks.

Summary updated

Abstract

A major goal of dynamical systems theory is the search for simplified descriptions of the dynamics of a large number of interacting states. For overwhelmingly complex dynamical systems, the derivation of a reduced description on the entire dynamics at once is computationally infeasible. Other complex systems are so expansive that despite the continual onslaught of new data only partial information is available. To address this challenge, we define and optimise for a local quality function severability for measuring the dynamical coherency of a set of states over time. The theoretical underpinnings of severability lie in our local adaptation of the Simon-Ando-Fisher time-scale separation theorem, which formalises the intuition of local wells in the Markov landscape of a dynamical process, or the separation between a microscopic and a macroscopic dynamics. Finally, we demonstrate the practical relevance of severability by applying it to examples drawn from power networks, image segmentation, social networks, metabolic networks, and word association.
BibTeX
@misc{yu2020severability,
  author = {Yun William Yu and Jean-Charles Delvenne and Sophia N. Yaliraki and Mauricio Barahona},
  title = {{Severability of mesoscale components and local time scales in dynamical networks}},
  year = {2020},
  eprint = {2006.02972},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.02972},
}
Figure