Community Integration Algorithms (CIAs) for Dynamical Systems on Networks

Abstract

Dynamics of large-scale network processes underlies crucial phenomena ranging across all sciences. Forward simulation of large network models is often computationally prohibitive. Yet, most networks have intrinsic community structure. We exploit these communities and propose a fast simulation algorithm for network dynamics. In particular, aggregating the inputs a node receives constitutes the limiting factor in numerically simulating large-scale network dynamics. We develop community integration algorithms (CIAs) significantly reducing function-evaluations. We obtain a substantial reduction from polynomial to linear computational complexity. We illustrate our results in multiple applications including classical and higher-order Kuramoto-type systems for synchronisation and Cucker--Smale systems exhibiting flocking behaviour on synthetic as well as real-world networks. Numerical comparison and theoretical analysis confirm the robustness and efficiency of CIAs.

12 pages, 6 figures

References in corpus (7)

• Fast unfolding of communities in large networks
• The structure and dynamics of multilayer networks
• Statistical Mechanics of Community Detection
• Networks beyond pairwise interactions: structure and dynamics
• Community structure in directed networks
• On the Random Batch Method for second order interacting particle systems
• On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs