Linear stability analysis for large dynamical systems on directed random graphs

Abstract

We present a linear stability analysis of stationary states (or fixed points) in large dynamical systems defined on random directed graphs with a prescribed distribution of indegrees and outdegrees. We obtain two remarkable results for such dynamical systems: First, infinitely large systems on directed graphs can be stable even when the degree distribution has unbounded support; this result is surprising since their counterparts on nondirected graphs are unstable when system size is large enough. Second, we show that the phase transition between the stable and unstable phase is universal in the sense that it depends only on a few parameters, such as, the mean degree and a degree correlation coefficient. In addition, in the unstable regime we characterize the nature of the destabilizing mode, which also exhibits universal features. These results follow from an exact theory for the leading eigenvalue of infinitely large graphs that are locally tree-like and oriented, as well as, for the right and left eigenvectors associated with the leading eigenvalue. We corroborate analytical results for infinitely large graphs with numerical experiments on random graphs of finite size. We discuss how the presented theory can be extended to graphs with diagonal disorder and to graphs that contain nondirected links. Finally, we discuss the influence of small cycles and how they can destabilize large dynamical systems when they induce strong enough feedback loops.

Typo's have been corrected in the equations (C3), (C8) and(C9), and the caption of Figure 5. The original manuscript also interchanged sOut for sIn, and conversely, which affects Eqs.(56), (60), (D10), (H1), and (H4)

References in corpus (52)

• Power-law distributions in empirical data
• Spatial Networks
• Stability Criteria for Complex Ecosystems
• Dynamics of Rumor Spreading in Complex Networks
• Spectral redemption: clustering sparse networks
• Virality Prediction and Community Structure in Social Networks
• Statistical physics of inference: Thresholds and algorithms
• Localization and Spreading of Diseases in Complex Networks
• Pathways towards instability in financial networks
• Transition to chaos in random neuronal networks
• Around the circular law
• Google matrix analysis of directed networks
• Approximating the largest eigenvalue of network adjacency matrices
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Transition to chaos in random networks with cell-type-specific connectivity
• The circular law for random matrices
• Instabilities in complex mixtures with a large number of components
• Non-Hermitian Localization in Biological Networks
• Nonlinear Analogue of the May-Wigner Instability Transition
• Loops of any size and Hamilton cycles in random scale-free networks
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• The effect of population abundances on the stability of large random ecosystems
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• On the localization transition in symmetric random matrices
• May's Instability in Large Economies
• Non-Hermitian Euclidean random matrix theory
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
• Constrained Markovian dynamics of random graphs
• Spectra of networks containing short loops
• Immune networks: multi-tasking capabilities near saturation
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Emergence of the giant weak-component in directed random graphs with arbitrary degree distributions
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Spectra of sparse regular graphs with loops
• On the low dimensional dynamics of structured random networks
• Eigenvalue method to compute the largest relaxation time of disordered systems
• Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices
• On random symmetric matrices with a constraint: the spectral density of random impedance networks
• Spectral density of random graphs with topological constraints
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• Universal transient behavior in large dynamical systems on networks
• Eigenvalue spectra of large correlated random matrices
• Universal hypotrochoidic law for random matrices with cyclic correlations
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Algorithmic detectability threshold of the stochastic block model
• Top Eigenpair Statistics for Weighted Sparse Graphs
• Glassy dynamics on networks: local spectra and return probabilities
• Subpopulations and Stability in Microbial Communities
• Fat-tailed distribution derived from first eigenvector of symmetric random sparse matrix

Cited by in corpus (25)

• Network structural origin of instabilities in large complex systems
• Localization and universality of eigenvectors in directed random graphs
• Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
• Composition Dependent Instabilities in Mixtures With Many Components
• Nonlinearity-generated Resilience in Large Complex Systems
• The spectral density of dense random networks and the breakdown of the Wigner semicircle law
• Eigenvalue spectra and stability of directed complex networks
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Stability of large complex systems with heterogeneous relaxation dynamics
• Instabilities of complex fluids with partially structured and partially random interactions
• Dynamical Mean-Field Theory of Complex Systems on Sparse Directed Networks
• Antagonistic interactions can stabilise fixed points in heterogeneous linear dynamical systems
• Real spectra of large real asymmetric random matrices
• Analytic solution of the two-star model with correlated degrees
• Spectral properties, localization transition and multifractal eigenvectors of the Laplacian on heterogeneous networks
• Local sign stability and its implications for spectra of sparse random graphs and stability of ecosystems
• Eigenvalue spectral tails and localization properties of asymmetric networks
• Random matrix ensemble for the covariance matrix of Ornstein-Uhlenbeck processes with heterogeneous temperatures
• Epidemic threshold and localization of the SIS model on directed complex networks
• Contribution of directedness in graph spectra
• Interbank network reconstruction enforcing density and reciprocity
• Understanding random-walk dynamical phase coexistence through waiting times
• Connected components in networks with higher-order interactions
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Spectral signatures of structural change in financial networks