betaFeedback

WorksPhysics and Astronomy

Dynamics-preserving graph sparsification

Abstract

Many dynamical systems unfold on networks of nodes coupled by edge interactions. This work is motivated by the following question: can we remove most edges from a networked dynamical system without significantly altering its behavior? For a given network, our goal is to find a sparser network that approximately preserves the dynamics on the nodes. We first study linear diffusion, where node values evolve according to the graph Laplacian. The dominant network sparsification method, effective resistance sampling, preserves all Laplacian eigenvalues within a uniform multiplicative bound. We show that with a limited edge budget, this is dynamically inefficient: diffusion is dominated by the slowest-decaying modes, so enforcing a uniform guarantee spends edges on fast modes that barely affect long-term dynamics. Based on this observation, we derive Diffusion Spectral Error (DSE), which evaluates in closed form the typical error in trajectories between the original and sparsified graphs over random initial conditions. Minimizing this error, which naturally prioritizes slow modes, yields sparse networks explicitly designed to preserve dynamics. At the same sparsification levels, DSE sparsification often preserves diffusion dynamics with several-fold lower error than effective resistance sampling, and up to two orders of magnitude lower on strongly modular networks. Although derived in a linear context, we empirically find that DSE sparsification gives similar improvements in the Kuramoto model (a nonlinear system of coupled oscillators), where DSE sparsification approximately preserves the synchronization threshold and, at strong coupling, order-parameter trajectories.

Paper details

vlnc:W_nmdkkytz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…