Community Integration Algorithms (CIAs) for Dynamical Systems on Networks
arXiv:2203.16657 · doi:10.1016/j.jcp.2022.111524
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.
arXiv comment12 pages, 6 figures
References in corpus (15)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- The structure and function of complex networks
- Finding community structure in very large networks
- The structure and dynamics of multilayer networks
- Collective motion
- Temporal Networks
- Statistical Mechanics of Community Detection
- Networks beyond pairwise interactions: structure and dynamics
- Community structure in directed networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Topological Evolution of Dynamical Networks: Global Criticality from Local Dynamics
- Significant Scales in Community Structure
- 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