PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamical Systems on Networks: A Tutorial

Mason A. Porter, James P. Gleeson

arXiv:1403.7663v2nlin.AOcond-mat.dis-nncond-mat.stat-mechcs.SIphysics.soc-ph

TL;DR

The paper addresses how network connectivity shapes dynamical processes and provides a tutorial centered on analytically tractable network models. It synthesizes examples, approximation methods, software, and time-dependent networks, showing that dynamics and network structure can interact in varied ways.

  • Problem

    The central question is how underlying nontrivial connectivity affects dynamical processes on networks.

  • Method

    The paper uses analytically tractable examples, theoretical approximations, software overviews, and discussions of time-dependent networks to teach network dynamical systems.

  • Results

    The tutorial covers popular model families, analytical approximation techniques, software implementations, and time-scale challenges in dynamical networks.

  • Takeaways & Limitations

    The paper provides a foundation for studying network dynamics and for understanding the scope and validity of mean-field, pair, and higher-order approximations.

  • Takeaways & Limitations

    Mean-field treatment may fail when degree classes contain substantial modularity or other sources of node diversity, and locally tree-like assumptions constrain structural realism.

Abstract

from arXiv · show

We give a tutorial for the study of dynamical systems on networks. We focus especially on "simple" situations that are tractable analytically, because they can be very insightful and provide useful springboards for the study of more complicated scenarios. We briefly motivate why examining dynamical systems on networks is interesting and important, and we then give several fascinating examples and discuss some theoretical results. We also briefly discuss dynamical systems on dynamical (i.e., time-dependent) networks, overview software implementations, and give an outlook on the field.

I. PREAMBLE

The tutorial examines how nontrivial network connectivity affects dynamical processes, emphasizing analytically tractable examples while connecting them to more complex systems. It introduces foundational concepts, model families, analytical approximations, software, and time-dependent networks.

  • The tutorial focuses on simple, analytically tractable situations because they provide insight and springboards for studying more complicated systems.
  • Network connectivity can alter dynamical processes, including contagion prevalence, synchronization, and viral spread.
  • Binary-state network dynamics are especially tractable, and mean-field methods can produce analyzable ODE systems for expected infected populations.
  • The article covers network representations, discrete- and continuous-state examples, synchronous versus asynchronous updates, percolation, software, and dynamical networks.
  • The discussion largely uses unweighted, undirected networks and gives minimal treatment to directed, weighted, temporal, and multilayer structures.

4. “Explosive” Percolation

The paper presents percolation and compartmental contagion models as tractable network dynamical systems, then situates them among extensions and data-driven approaches. These examples clarify both analytical opportunities and realism limits.

  • 4. “Explosive” Percolation: Explosive percolation processes have very steep transitions, but Achlioptas processes have been demonstrated to remain continuous.
  • 4. “Explosive” Percolation: In an Achlioptas process, one repeatedly samples two possible edges and selects one according to a rule affecting giant-component development.
  • 4. “Explosive” Percolation: Research continues on Achlioptas processes across substrate networks and selection rules, especially rules avoiding global graph information.
  • Compartmental models represent states such as susceptible, infected, and recovered, with parameters specifying transition rates.
  • In SI dynamics, transmission across each infected-susceptible edge occurs at hazard rate λ, giving a susceptible node with m infected neighbors infection rate λm.
  • SIS permits recovery from infected to susceptible, whereas SIR transfers infected nodes to a recovered state that cannot be reinfected.
  • These contagion models are analytically tractable and illustrative of network-structure effects, but are grossly unrealistic in most biological settings.
  • More detailed compartmental models, non-Markovian epidemics, simulations, and real-data analyses complement the simple analytical approaches.

5. Other Uses of Compartmental Models

The section surveys compartmental and social-influence models, emphasizing the difficulty of identifying causal mechanisms in behavioral diffusion. It contrasts tractable threshold and opinion models with richer but more complex formulations.

  • Compartmental models have also been applied to zombification and social influence, although they are not the dominant approach for social topics.
  • Social influence can resemble biological contagion, but distinguishing genuine spread from homophily and environmental effects is difficult.
  • Control strategies depend on the relative contributions of social influence, homophily, environmental effects, or their combination.
  • Simple tractable models deliberately avoid confounding putative social influence with processes that genuinely spread through networks.
  • Threshold Models: Binary-state threshold models encode interdependence and heterogeneity through neighbor-dependent updates and fixed node thresholds.
  • Threshold Models: Centola-Macy models use the number of active neighbors, while Watts models use the fraction of infected neighbors relative to node degree.
  • Threshold Models: Watts and Centola-Macy models are monotonic, which helps derive accurate approximations, but their hub behavior can differ qualitatively.
  • Other Models: Threshold models are mathematically tractable but overly simplistic because they omit repeated individual signals and more microscopic social reinforcement.

D. Voter Models

The voter model is an analytically tractable binary-state network process with many variants and application-relevant behavior. Its outcomes depend on both the update rule and network structure, while simulation requires careful choices about update timing and stochastic transitions.

  • Voter-model definition: The direct voter model randomly selects a node, which copies a uniformly selected neighbor’s binary opinion at each discrete time step.The two states are represented as +1 and −1.
  • Network-dependent outcomes: Consensus behavior depends on both the voter dynamics and the network architecture.The paper contrasts direct and edge-update voter dynamics on different network families.
  • Network-dependent outcomes: For direct voter dynamics on configuration-model networks, mean consensus time scales linearly with N when γ > 3 and sublinearly when γ ≤ 3.For edge-update dynamics on BA networks, consensus time instead depends linearly on N for any exponent.
  • Voter-model variants: The constrained voter model has three states—Left, Right, and Center—and permits interactions only involving centrists.Extremists refuse to interact with one another, and the complete-graph setting gives a mean-field limit.
  • Simulation implementation: Asynchronous updating changes only one node per time step, limiting the fraction of active nodes’ change to at most 1/N.In a vanishing-update-fraction limit, such dynamics can be accurately described by coupled differential equations.
  • Simulation implementation: Hazard-rate simulations require care because a node changing at rate Fi has transition probability Fi dt over an infinitesimal interval.Taking dt → 0 yields exponential survival times for Markov processes, and event-driven Gillespie methods can accelerate some simulations.

G. Other Dynamical Processes

The tutorial surveys additional network dynamical processes and highlights both established applications and open areas. It emphasizes that network structure can produce counterintuitive dynamical outcomes and that PDEs on networks remain comparatively understudied.

  • Stability and control: General methods have been used to study stability and control across many continuous and discrete dynamical systems on networks.Applications include synchronization of chaotic systems such as Rössler circuits.
  • Open directions: Compared with ODEs on networks, comparatively little work has addressed PDEs on networks, although scholarship on both linear and nonlinear PDEs is increasing.Traffic flow and shock-forming PDEs are identified as promising examples.
  • Applications: Financial contagion and systemic risk can be modeled with threshold processes on directed banking networks, where weighted edges represent interbank-loan values.Weighted edges become important for increasingly realistic models.
  • Applications: Coordination games on networks are related to threshold models, including technology-adoption choices between alternative communication technologies.The example frames technologies as game strategies selected by network nodes.
  • Applications: Neural signal-propagation models use neuronal network structure to examine how topology affects dynamics and potentially functional behavior.Synchronization properties across different network topologies are a central concern.
  • Counterintuitive effects: Increasing edge coupling or adding coupling edges can lower, rather than raise, synchrony in some animal-behavior models.The tutorial identifies this as a broader feature recently noted for dynamical systems on networks.

V. GENERAL CONSIDERATIONS

The paper now shifts from specific network dynamical models to general considerations, building on ideas introduced earlier.

  • General considerations: The tutorial introduces general considerations after discussing several specific dynamical-process families.These considerations extend ideas previously mentioned in the paper.
  • General considerations: The discussion uses earlier model examples as motivation for a broader treatment of network dynamics.The transition explicitly presents the preceding examples as interesting in their own right.
  • General considerations: The section provides a conceptual bridge from model-specific discussions to general analytical ideas.The paper signals that several of these ideas were already foreshadowed in prior sections.

A. Master Stability Condition and Master Stability Function

The tutorial develops master stability conditions and functions that connect network spectra to the local stability of dynamical states. Under simplifying assumptions, linear stability decomposes into eigenmode-specific conditions that can be evaluated analytically or numerically.

  • Framework: Master stability analysis relates qualitative network dynamics to adjacency-matrix eigenvalues and provides necessary and sufficient conditions for linear stability.The framework can also use graph-Laplacian eigenvalues and is widely applied to synchronization in coupled oscillators.
  • Linear stability: Diagonalizing the linearized matrix decomposes perturbations into eigenmodes whose amplitudes satisfy α̇_r = μ_rα_r and evolve as α_r(t) = α_r(0) exp(μ_rt).Local asymptotic stability requires Re(μ_r) < 0 for every mode; any positive real part implies instability.
  • Scalar dynamics: For the scalar simplified model, stability requires every eigenvalue of P := aI + cA to be negative.Because P is symmetric, its eigenvalues are real and equal to a + cλ_r, where λ_r are adjacency-matrix eigenvalues.
  • Master stability condition: The master stability condition separates network structure from node and coupling dynamics: the outer terms depend on network structure, while the central term depends on functional forms.This separation makes adjacency spectra useful for analyzing dynamical behavior across networks.
  • Master stability function: For multidimensional node dynamics, the master stability function σ(λ) is the largest positive real part among eigenvalues of the reduced matrix and stability requires σ(λ_r) < 0 for all r.The function is described as readily evaluable numerically, enabling analysis of more complex node states.

B. Other Approaches for Studying Dynamical Systems on Networks

Beyond master stability methods, the tutorial surveys approaches that connect network architecture with dynamical behavior. These include graph-based stability tests, coupled-cell and multilayer formalisms, spectral transformations, and algebraic methods.

  • Stability approaches: Spanning trees of the Coates graph of a Jacobian can provide necessary conditions for the stability of a dynamical state.The Coates graph is formed by removing self-edges from the network representation of the Jacobian.
  • Network formalisms: Coupled-cell networks represent coupling structure and cell equivalence, while multiarrow formalisms allow multiple connection types and support multilayer-network analysis.These formalisms extend structural analysis beyond single-layer graphs.
  • Algebraic approaches: Isospectral transformations and algebraic-geometry methods are used to characterize qualitative and quantitative behavior in dynamical systems on networks.Applications include studying equilibria and, more recently, network behavior quantitatively with data, computational algebra, and statistics.

C. Discrete-State Dynamics: Mean-Field Theories, Pair Approximations, and Higher-Order Approximations

The tutorial introduces approximation schemes for stochastic discrete-state dynamics that estimate network-scale observables from node-level processes. Mean-field, pair, and higher-order approaches trade tractability and lower dimensionality against assumptions and approximation complexity.

  • Purpose of approximations: Approximation schemes aim to predict emergent network-scale observables, such as infected-node counts, from local stochastic discrete-state dynamics.Mathematical tractability can make these theories useful for analysis.
  • Mean-field theory: Mean-field theories are common because they are relatively straightforward to formulate and can achieve reasonable or sometimes very high accuracy.Accuracy is commonly assessed by comparing theoretical predictions with large-scale Monte Carlo simulations.
  • Node-based approximations: Node-based SI equations are large and unclosed because infection probabilities involve joint susceptible-infected terms that require approximation or additional evolution equations.Assuming independence closes the system at first moments and yields a mean-field theory.
  • Pair and higher-order approximations: Pair approximations retain pair-level quantities but introduce triplet terms, creating a hierarchy that must be truncated or extended with further dynamical equations.Bayes-theorem-based approximations provide one explicit way to close the pair equations.
  • Moment closure: Moment closure requires truncating a hierarchy of differential equations, with higher-order schemes offering an alternative to simpler closure assumptions.The tutorial points to algebraic methods as another approach to moment closure.

2. Degree-Based MF Approximation for the SI Model

Degree-based mean-field approximation reduces the SI model by treating nodes with the same degree as dynamically similar. The resulting system has one equation per degree class and becomes a single logistic equation on a regular network.

  • Degree-based approximation: Degree-based approximation assumes that nodes of degree k have sufficiently similar dynamics to be represented by the infected fraction ρ_k(t).This reduces node-level variables by grouping nodes according to degree.
  • Closure assumptions: The approximation replaces the node-level neighbor sum with kω, where ω is the probability that a randomly selected edge endpoint is infected.Using P_k in this construction assumes a configuration-model network.
  • Dimensional reduction: The degree-based SI system contains one equation per degree class, typically far fewer than the N node-level equations.For a z-regular network, the system reduces to one equation for the infected fraction ρ(t).
  • Regular networks: On a z-regular network, the reduced SI equation is the analytically solvable logistic differential equation used for homogeneous, well-mixed populations.The tutorial later considers a hierarchy of approximation schemes with successively better accuracy.

3. Degree-Based MF Approximation for a Threshold Model

The paper derives a mean-field approximation for a Watts threshold model by treating neighbor and node-state events as independent, then compares its predictions with simulations and higher-accuracy schemes. The approximation can be qualitatively wrong on sparse networks, motivating pair, motif, and compartmental approaches.

  • Mean-field derivation: The mean-field derivation considers asynchronous updates on z-regular networks and tracks the active-node fraction ρ(t) from a random initial seed fraction.A node activates when its active-neighbor fraction m/z reaches its threshold R.
  • Mean-field assumptions: The first mean-field assumption makes neighbors independently active with probability ρ(t), yielding a binomial distribution for the number of active neighbors.The paper notes that this assumption fails exactly on networks containing triangles or other short cycles.
  • Mean-field equation: The resulting nonlinear ODE for ρ(t) can be solved numerically to produce time-dependent mean-field predictions.The derivation combines the probability of an inactive updating node, its active-neighbor count, and the threshold CDF.
  • Comparison with simulations: For z = 6 and z = 7, mean-field predictions are qualitatively correct but quantitatively poor; for z = 4, they incorrectly predict contagion across the whole network.The comparison uses stochastic simulations alongside pair approximation and approximate master equation schemes.
  • Accuracy and extensions: Mean-field assumptions omit local clustering, dynamical correlations, and modularity, limiting accuracy especially for sparse networks and bifurcation analysis.Pair approximations incorporate joint states across random edges, while motif and compartmental approaches include progressively more neighborhood information.
  • Accuracy and extensions: Mean-field and generalized theories reduce network dynamical systems to lower-dimensional approximate systems, providing analytically tractable alternatives to direct computation.The paper contrasts these reductions with computational approaches that use only simulations.

D. Additional Considerations

The paper surveys extensions and practical considerations for dynamical systems on networks, including higher-order approximations, simulation software, and time-dependent or adaptive networks. It emphasizes that temporal network structure can substantially alter dynamical behavior and that important theoretical challenges remain.

  • Additional theoretical considerations: Approximation methods have incorporated degree correlations, clustering, modularity, and multilayer structure, but extending high-accuracy theories beyond binary-state dynamics remains challenging.Open problems include continuum-valued states and non-monotonic binary dynamics with synchronous updates.
  • Simulation and software: Monte Carlo simulation of stochastic discrete-state dynamics is straightforward, and monotonic threshold models can update nodes asynchronously using adjacency-matrix calculations.The simulation computes infected-neighbor counts, compares m_i/k_i with each threshold, and iterates until no further infections are possible.
  • Simulation and software: For monotonic threshold dynamics, the steady state is independent of asynchronous versus synchronous updating, allowing simultaneous updates when only the final state matters.The paper also points to software for solving approximate master equation systems and simulating time-dependent networks.
  • Time-dependent networks: Network and nodal dynamics can operate on fast, slow, or comparable time scales, with the last case producing adaptive networks where neither dynamics can be ignored.Static-network assumptions are appropriate only when network changes are sufficiently slow relative to nodal dynamics.
  • Time-dependent networks: Temporal-network dynamics can alter effective interaction weights and produce behavior different from static networks obtained by averaging interactions.The paper highlights bursty, non-Poisson interaction patterns and the need for suitable computational techniques such as Gillespie algorithms.
  • Time-dependent networks: Adaptive SIS and adaptive voter models illustrate how network rewiring and nodal dynamics can be analyzed together using compartmental approaches.For adaptive SIS, AME predictions agree very well with numerical simulations.

VIII. OTHER RESOURCES

The article points readers toward complementary tutorials, reviews, textbooks, and specialized literature while emphasizing that it is not a comprehensive review. It closes by identifying analytical, time-dependent, and multilayer network dynamics as important open directions.

  • Complementary resources: The recommended resources span introductions, textbooks, reviews, and specialized treatments of epidemic, social, multilayer, and critical phenomena on networks.The list includes resources with different levels of technical depth and perspectives.
  • Open analytical problems: Analytical techniques remain challenging because mathematically rigorous results are rare and much existing work concerns percolation-like toy problems.The authors call for studying the next easiest systems and moving beyond percolation-related models.
  • Time-dependent networks: Time-dependent networks require attention to the balance between dynamics on networks and network dynamics, while many studied examples remain unrealistic.The authors identify analytical-method validity and time-scale choices as important issues.
  • Multilayer networks: Multilayer networks offer problems involving multiple edge types and structural or dynamical correlations, but their study is still in its infancy.The authors describe multilayer dynamical systems as a rich and developing research area.

Appendix: High-Accuracy Approximation Methods for General Binary-State Dynamics

This section presents a unified framework for stochastic binary-state dynamics and derives mean-field, pair-approximation, and higher-order equation systems. These formulations cover many established models, with pair approximations typically improving accuracy over mean-field equations.

  • General framework: Binary-state dynamics assign each node one of two states and use local stochastic transition rates determined by node degree and infected-neighbor count.Susceptible-to-infected and infected-to-susceptible transitions use infection rates Fk,m and recovery rates Rk,m.
  • Model coverage: The framework encompasses models including Bass diffusion, Ising spins, majority vote, threshold opinions, SIS disease spread, and the voter model.Different models are represented through their infection and recovery rate functions.
  • Mean-field approximation: Mean-field equations form a closed system of kmax + 1 nonlinear differential equations when degree classes run from 0 through kmax.Standard numerical methods can solve these equations efficiently.
  • Approximate master equations: Approximate master equations divide nodes by state and infected-neighbor count but yield a high-dimensional closed nonlinear system for general binary-state dynamics.The AME formulation has [(kmax + 1)(kmax + 2)] equations.

3. Monotonic Dynamics and Response Functions

For monotonic threshold dynamics, the high-dimensional approximate master equation system reduces exactly to two ordinary differential equations. These equations accurately predict infection dynamics and support analytical study of response functions and related percolation problems.

  • Monotonic threshold dynamics: Monotonic dynamics permit only one-way transitions, so recovery rates satisfy Rk,m ≡ 0.Threshold dynamics activate a node when its infected-neighbor count reaches or exceeds its threshold.
  • Monotonic threshold dynamics: Threshold activation is deterministic once an updating node has at least Mk infected neighbors, with degree and node type jointly determining the threshold.The feature vector combines node degree and type, allowing heterogeneous threshold populations.
  • Exact reduction: The approximate master equation system reduces exactly to 2 ODEs for monotonic threshold dynamics, avoiding approximation in this special case.The resulting two-dimensional system is more accurate than naive pair or mean-field theories.
  • Accuracy and validation: Solving the 2D system yields the infected fraction ρ(t) with very high accuracy and closely matches numerical simulations.The AME and reduced-system curves are identical in the reported examples.
  • Response functions: The response-function formulation reproduces known bond-percolation equations for the fractional size of the giant connected component.This connects monotonic dynamical analysis with generating-function results for percolation.

c. Cascade Conditions

The cascade analysis uses local instability of the no-infection equilibrium to derive a condition for global cascades in the Watts threshold model. The condition combines network degree structure with node responsiveness to a single infected neighbor.

  • Cascade mechanism: The reduced equations analyze whether a vanishingly small seed can destabilize the infection-free equilibrium and generate a global cascade.The equilibrium at (ρ, φ) = (0, 0) represents complete absence of infection.
  • Stability analysis: Local instability is determined by the one-dimensional φ system, with instability occurring if and only if the linear-stability condition is satisfied.The corresponding ρ values become strictly positive under the stated monotonicity conditions.
  • Cascade condition: The Watts-model cascade condition combines the degree distribution Pk with the expected response f(k, 1) of degree-k nodes to one infected neighbor.It therefore incorporates both network topology and node-level dynamics.
  • Operational definitions: Cascade definitions may depend on reaching a minimum infected fraction or doing so within a specified finite time.The authors note that empirical and practical applications need not use the t →∞ criterion.
Loading 1403.7663v2…