Fundamentals of spreading processes in single and multilayer complex networks

Guilherme Ferraz de Arruda; Francisco A. Rodrigues; Yamir Moreno

Source-linked AI summary

Fundamentals of spreading processes in single and multilayer complex networks

Guilherme Ferraz de Arruda, Francisco A. Rodrigues, Yamir Moreno

arXiv:1804.08777v2Apr 23, 2018physics.soc-phcond-mat.stat-mechq-bio.PE

TL;DR

Spreading-process research needs methods that account for the structure of single and multilayer complex networks rather than relying only on homogeneous populations. This review formalizes epidemic models, classifies their time and updating schemes, and unifies analytical and simulation approaches. It provides a framework spanning mean-field methods, Monte Carlo comparisons, and simulation algorithms for epidemic-like processes.

Problem
Homogeneous population models do not adequately represent the heterogeneous and multilayer structures underlying real spreading systems.
Method
The review formalizes spreading processes on single and multilayer networks, classifies continuous-time and cellular-automata approaches, and presents MF, HMF, QMF, PQMF, and simulation techniques.
Results
The review relates PQMF and QMF analyses to non-backtracking matrices and message passing, and finds CA(RP) approaches highly precise against Monte Carlo simulations.
Takeaways & Limitations
The assembled methods provide a framework for studying epidemic-like processes theoretically and computationally across single-layer and multilayer complex networks.
Takeaways & Limitations
The review does not present a closed expression for the PQMF critical point in the general case, and alternative critical-point formulations diverge in many cases.

Abstract

from arXiv · show

Spreading processes have been largely studied in the literature, both analytically and by means of large-scale numerical simulations. These processes mainly include the propagation of diseases, rumors and information on top of a given population. In the last two decades, with the advent of modern network science, we have witnessed significant advances in this field of research. Here we review the main theoretical and numerical methods developed for the study of spreading processes on complex networked systems. Specifically, we formally define epidemic processes on single and multilayer networks and discuss in detail the main methods used to perform numerical simulations. Throughout the review, we classify spreading processes (disease and rumor models) into two classes according to the nature of time: (i) continuous-time and (ii) cellular automata approach, where the second one can be further divided into synchronous and asynchronous updating schemes. Our revision includes the heterogeneous mean-field, the quenched-mean field, and the pair quenched mean field approaches, as well as their respective simulation techniques, emphasizing similarities and differences among the different techniques. The content presented here offers a whole suite of methods to study epidemic-like processes in complex networks, both for researchers without previous experience in the subject and for experts.

1. Introduction

Classical homogeneous-mixing epidemic models poorly represent the heterogeneous and multilayer structures of real populations. This review addresses that gap by organizing network-based spreading theory, simulations, and mean-field approaches for single and multilayer systems.

Homogeneous mixing assumes equal connection probabilities between individuals, unlike the heterogeneous contact patterns common in real systems.
Representing individuals as nodes and relationships as edges incorporates network structure into epidemic-process models.
Multilayer-network theory extends spreading analysis to systems containing multiple constituents or interaction types.
Heterogeneous structures alter the predicted dynamics of disease spreading, including epidemic thresholds in scale-free networks.
The review compiles theoretical and computational tools for disease and epidemic-like modeling on single-layer and multilayer networks.

2. Classical network theory

Classical network theory represents systems as graphs and characterizes them through structural measurements and generative models. The review emphasizes adjacency-matrix representations, node- and network-level measures, and examples linking topology to spreading processes.

Network representation: A network is represented as a graph of nodes and edges, often encoded by an adjacency matrix whose entries indicate connections.
Network representation: The review focuses on finite, undirected, unweighted, connected networks, while extensions to other types are stated explicitly.
Structural characterization: Centrality measures compare nodes within a network, whereas global measurements compare different networks.
Centrality measures: Degree, betweenness, PageRank, clustering, k-shell, eigenvector, closeness, and neighborhood measures capture different aspects of node position and influence.
Centrality measures: In the São Carlos road network, betweenness centrality captures peripheral long roads that other centrality patterns neglect.
Accessibility: Generalized random-walk accessibility uses a matrix exponential to calculate transition probabilities over walks of all lengths.

3. Spectral characterization of networks

The review characterizes network structure through adjacency, Laplacian, probability-transition, and non-backtracking matrices, linking their spectra to dynamical processes. It also presents spectral examples and computational reductions for these representations.

Adjacency matrix: The adjacency matrix completely describes a network and appears in the modeling of spreading processes.
Adjacency matrix: For sufficiently dense Erdös and Rényi networks, Wigner’s semicircle law describes the bulk adjacency spectrum.For n = 3000 and ⟨k⟩ = 10, Figure 7 compares the spectrum with this prediction.
Laplacian matrix: The Laplacian matrix has smallest eigenvalue zero, while its second smallest eigenvalue, algebraic connectivity, relates to community structure and network dynamics.
Probability transition matrix: The probability-transition matrix is closely related to random walks, spreading processes, clustering, and the Laplacian matrix.
Non-backtracking matrix: The non-backtracking spectrum is less sensitive to high-degree nodes, and its bulk is confined to a complex-plane disk of radius √c.Its relevant spectrum can be reduced to a 2N × 2N matrix, drastically reducing computational complexity.

4. Multilayer network theory

Multilayer networks represent different kinds of contact through interacting layers. The review focuses on multiplex and interconnected networks and introduces matrix and tensorial representations for their analysis.

Multilayer networks consist of interacting layers whose nodes and edges represent different kinds of contact.
The review focuses on multiplex and interconnected networks as two specific multilayer cases.
It introduces matrix and tensorial representations, emphasizing supra-adjacency matrices for multiplex networks.The multiplex case permits spectral analysis through symmetries in its representation.

GOOGLE +

The review formalizes multiplex networks using node-layer pairs, layer graphs, coupling graphs, supra-graphs, and supra-matrices. It then relates multiplex structure to quotient networks and eigenvalue interlacing.

Multiplex representation: A multiplex network is defined by layers, nodes, node participation, and a set of layer-graphs.A node-layer pair represents a node in a particular layer.
Multiplex representation: The coupling graph links node-layer pairs representing the same node across layers, forming disconnected cliques or isolated nodes.
Multiplex representation: The supra-graph is the union of layer graphs and the coupling graph, providing a synthetic representation of the multiplex network.A multiplex is fully aligned when all nodes participate in all layer graphs.
Supra-matrices: The supra-adjacency matrix combines intra-layer adjacency matrices with an interlayer coupling matrix whose strength can be weighted by parameter p.
Quotient networks: Adjacency eigenvalues of a quotient network interlace those of the parent network, with analogous results for Laplacian eigenvalues.
Spectral results: The multilayer adjacency tensor’s eigenvalue is at least as large as every eigenvalue of the isolated layers and the network of layers.

5. Epidemic spreading

The review models epidemic spreading as Markov dynamics with local state-transition rules and distinguishes continuous-time rates from discrete-time probabilities. It contrasts SI, SIS, SIR, and SIRS behavior.

Disease models: The SI model has a single absorbing all-infected state for every connected population with nonzero initial infection.
Disease models: In SIS, recovery returns individuals to susceptibility, leaving one absorbing inactive state in finite populations and permitting long-lived disease persistence.In the thermodynamic limit, the system remains trapped in the meta-state.
Disease models: SIR gives recovered individuals permanent removal from the dynamics and has infinitely many absorbing states in the thermodynamic limit.
Disease models: SIRS adds transitions from infected to recovered and from recovered to susceptible, but is less extensively explored because of its higher mathematical complexity.
Formal epidemic dynamics: Epidemic spreading is represented as a Markov chain whose configurations assign susceptible, infected, or recovered states to network nodes.
Time conventions: Continuous-time dynamics use independent Poisson processes with spreading and recovery rates, allowing the effective rate τ = λ/δ.In discrete time, λ and δ are probabilities, so this rescaling is not always possible.

6. Rumor spreading

The review introduces rumor spreading through the Daley–Kendall and Maki–Thompson models, distinguishing their contact mechanisms and extending analysis to related information-spreading models. It also formulates the dynamics using Markov chains and discusses continuous-time modeling.

Rumor models: The Daley–Kendall and Maki–Thompson models are identified as the two most common traditional rumor-spreading models.They classify individuals as ignorants, spreaders, and stiflers.
Rumor models: The Daley–Kendall model uses undirected contact mechanisms in which two contacting spreaders both become stiflers.This contrasts with the directed-contact mechanism of the Maki–Thompson model.
Extensions: A re-parameterized class of rumor models adds uninterested individuals and studies the final stifler fraction and its variance in finite populations.
Applications: Twitter-based studies of protest recruitment reported influential spreaders, while other complex-network evidence found no influential spreaders.These contrasting findings motivated two additional models.
Formalization: Rumor dynamics can be represented as a Markov chain over node configurations, while much of the literature models these processes in continuous time.The continuous-time formulation uses independent stochastic processes to describe transitions.

7. Exact SIS Markov chain

The exact SIS formulation represents every network infection configuration as a Markov-chain state and derives its evolution from infection and recovery processes. It provides exact dynamical and threshold insights, but solving the resulting 2^N equations is prohibitive for practical network sizes.

Model definition: The exact SIS model assigns infection events to directed edges at rate λ and recovery events to infected individuals at rate δ.The population is assumed to interact through an undirected, connected adjacency matrix A.
Model definition: The effective spreading rate is τ = λ/δ, reducing the dynamics to one control parameter after rescaling time by δ.The exact equations still depend on joint infection probabilities such as ⟨Y_iY_j⟩.
Exact Markov chain: The exact solution requires solving 2^N equations, making it prohibitive in practice and primarily valuable for physical insight and approximation development.The formulation can generate higher-order product equations, with independence assumptions entering the approximations.
Threshold behavior: The order parameter is the fraction of infected individuals, distinguishing inactive states with ρ = 0 from active states with ρ > 0 across the critical point.
Threshold behavior: Before the critical point, the disease decays exponentially fast when τ < 1/Λ_1, linking SIS dynamics to the largest adjacency-matrix eigenvalue.The solution is expressed through eigenvalues and constant matrices associated with the adjacency matrix.
Approximations: An approximate single nonlinear equation connects SIS evolution to the Laplacian, although the adjacency matrix provides the more natural representation for this process.
Exact Markov chain: Each SIS micro-state is encoded as a binary vector and mapped to an integer, with i = 0 representing no infected nodes and i = 2^N − 1 representing universal infection.This encoding supports construction of the exact Markov chain and its probability equations.
Threshold behavior: The finite SIS process has one absorbing state, the all-susceptible configuration, and therefore eventually reaches it as time tends to infinity.Above threshold, trajectories first approach a metastable state before slowly decaying toward absorption; below threshold, decay is fast.

8. Mean field approaches

The review compares mean-field approaches for epidemic spreading, from degree-based approximations to node- and pair-based formalisms, including extensions to multilayer networks. These approaches characterize thresholds, prevalence, localization, and approximation bounds through network structure and spectral properties.

Mean-field epidemic behavior: For R0 < 1, disease tends to die out, whereas for R0 > 1 it can persist in an endemic state.The non-zero stable solution above threshold represents a meta-stable state of the exact dynamics.
Quenched Mean Field: Quenched mean field models each node on a fixed network, using N equations while assuming independence between node states.Because infected neighbors positively correlate with infection states, QMF is an upper bound to the exact equation and improves on HMF estimates.
Multilayer networks: Quenched formalisms preserve a single fixed multilayer structure, whereas applying HMF to multilayer networks would collapse it into a community-structured network with heterogeneous spreading rates.For multilayer epidemic formulations, the critical point is determined by the largest eigenvalue of the interlayer rate matrix or its tensor counterpart.
Spectral analysis: Near the epidemic threshold, the QMF stationary prevalence follows the leading eigenvector of the adjacency matrix, while solutions are zero below threshold and non-zero above it.The leading eigenvector also supports an inverse-participation-ratio diagnosis of whether disease activity is localized around hubs or distributed across the network.
Pair Quenched Mean Field: PQMF improves QMF by providing a better upper bound to the average value and develops equations connected to the non-backtracking matrix and message passing.The review also discusses numerical exploration and critical-point predictions for this formulation.

8.5. Recurrent-state message-passing approach

The recurrent-state message-passing approach extends message passing to recurrent epidemic dynamics, while comparisons with PQMF and cellular-automaton methods clarify approximation choices and limitations.

Recurrent-state message passing: Recurrent-state message passing models SIS-like dynamics with node infection probabilities and conditional infection probabilities from neighbors.Unlike SIR, SIS permits recurrent state changes, so standard message passing does not translate directly.
Critical point prediction: Linear stability analysis of the recurrent-state equations yields a critical point expressed through the leading eigenvalue of the non-backtracking matrix.The resulting analysis agrees with the alternative PQMF derivation.
Comparison with PQMF: The comparison with PQMF shows that the formalisms use different approximations and that recurrent-state message passing neglects the interaction term λ⟨X_iY_j⟩.The recurrent-state formulation avoids this edge contribution by construction, whereas it appears naturally in pair-based summations.
Comparison with PQMF: Because of the neglected interaction term, recurrent-state message passing is neither a lower nor an upper bound, although it performed well in the reported simulations.Those experiments used the karate club network with N = 34 and an Erdős–Rényi network with N = 100 and average degree ⟨k⟩ = 3.
Cellular automata: Cellular automata use discrete-time updates, with λ and δ interpreted as probabilities rather than continuous-time rates.The synchronous SIS formulation can include reinfection within the same time step.
Multilayer networks: Multilayer spreading is more efficient, or at worst equally efficient, than spreading on the corresponding aggregate network when efficiency is measured by the critical point.This conclusion is limited to the critical point and does not characterize the whole phase diagram.
Simulation methods: The asynchronous simulation method captures spreading features but does not predict time correctly and is mainly applicable to steady-state analysis.More sophisticated simulation methods are presented elsewhere in the review.
Multilayer networks: Mean-field and heterogeneous mean-field treatments can erase multilayer structure by making groups statistically equivalent, motivating QMF and PQMF approaches that preserve it.The same coarse-graining can make a multilayer network indistinguishable from a single-layer network with community structure.

9. Comparison of continuous-time and cellular automaton models

The review compares continuous-time and synchronous cellular-automaton models through their Markov-chain transition matrices. They represent different processes, yet a first-order cellular-automaton approximation without reinfections shares the same critical point as QMF.

Model comparison: Continuous-time processes allow only one event at a time, whereas cellular automata perform node contacts during a discrete time interval.Thus, translating continuous-time rates directly into cellular-automaton probabilities does not always preserve the same process.
Sampled-time Markov chain: The infinitesimal-generator formulation of QMF produces a sampled-time Markov chain and its transition probability matrix.The discretization uses Δt as the time interval, with δΔt and λΔt representing recovery and spreading probabilities.
Sampled-time Markov chain: For Δt < 1/max_i q_i, the sampled-time Markov chain is exact for the QMF model, with a sampling rate above the fastest transition rate.This condition controls the discretization interval relative to the generator’s transition rates.
Transition-matrix comparison: The sampled-time QMF chain and the cellular-automaton chain have different transition matrices, so they represent different processes despite sharing local SIS rules.Their correspondence must therefore be assessed through the transition matrices rather than by matching parameters alone.
Shared critical point: A first-order approximation of the cellular automaton without reinfections has the same transition matrix as QMF, explaining their identical critical point.The review does not determine which model is more suitable for a particular application.
Interpretation: MF, QMF, and PQMF are coarse-grained versions of the same Markov chain and should be understood as approximations of that process.This frames their similarities as relationships among approximations rather than evidence that they define identical dynamics.

10. Monte Carlo simulations

The review presents continuous-time and cellular-automaton simulation techniques for spreading processes, including quasi-stationary methods and comparisons with mean-field approximations. Accuracy varies by dynamics and network structure: PQMF is generally precise, while QMF can fail for MT processes and some correlated structures.

Simulation approaches: The simulations cover continuous-time dynamics, cellular automata, quasi-stationary algorithms, and comparisons among QMF, PQMF, and Monte Carlo methods.The computational discussion focuses on multilayer networks, with single-layer cases treated as special cases.
Quasi-stationary evaluation: The quasi-stationary distribution captures active-state behavior, locates critical points through susceptibility peaks, and converges to the order parameter in the thermodynamic limit.Before the critical point, its distribution concentrates on a finite number of infected individuals.
Quasi-stationary evaluation: In finite systems, increasing time raises the probability of reaching the absorbing state while leaving the distribution average unchanged around a fluctuating meta-state.The example uses N = 100 nodes to emphasize finite-size effects.
Finite-size and structural effects: For Erdős–Rényi networks, the critical point remains fixed with system size, while susceptibility grows, suggesting a second-order phase transition.In star graphs, the critical point tends to zero with increasing size and QMF is inaccurate.
Accuracy evaluation: PQMF errors are consistently small, whereas QMF performs poorly for MT dynamics and faces greater challenges in assortative structures.In dense graphs, QMF is expected to improve as dynamical correlations diminish, while PQMF becomes computationally costly.
Accuracy evaluation: In multilayer networks, PQMF again yields consistently small errors and is the appropriate choice for MT dynamics, while QMF usually predicts behavior qualitatively and acts as an upper bound.Changing the interlayer coupling parameter η produced little difference in the observed results.
Accuracy evaluation: CA(RP) methods show remarkably small errors, although SIR has the largest error among the studied cellular-automaton approaches and CP cases perform poorly.The CA approach is first order, yet its RP error is comparable to second-order continuous-time models.

11. Finite size analysis

The review uses QS-based finite-size scaling to examine SIS dynamics on uncorrelated power-law networks with ζ=2.25, 2.75, and 3.5, then compares numerical critical points with HMF, QMF, PQMF, and message-passing predictions.

Method: Finite-size experiments estimate susceptibility and order-parameter scaling from QS simulations across system sizes.The analysis fits susceptibility peaks and related quantities as functions of N.
Network cases: Three uncorrelated power-law degree distributions are studied: P(k)∼k^-2.25, P(k)∼k^-2.75, and P(k)∼k^-3.5.The ζ=3.5 case uses a rigid cutoff to suppress outlier effects.
Mean-field comparisons: For ζ=2.25, HMF and QMF coincide, while PQMF and recurrent message passing share the same scale; inverse non-backtracking eigenvalue predictions are most accurate.The reported ordering is inverse leading non-backtracking eigenvalue, PQMF, HMF, then QMF.
Mean-field comparisons: For ζ=2.75, QMF and PQMF scale correctly, with PQMF providing a very good critical-point approximation, whereas HMF and non-backtracking predictions tend toward incorrect large-system behavior.The review reports agreement with earlier validation of PQMF in this case.
Mean-field comparisons: For ζ=3.5 with a rigid cutoff, none of the predictions follows the correct trend, although HMF and non-backtracking approaches perform better than the others.The authors characterize this as a simplified case in which degree-distribution outliers play a smaller role.

12. A brief comment on the nature of the critical point

The review relates the nature of epidemic critical points to eigenvector localization and hub reinfection, contrasting delocalized endemic activity with localized or slowly decaying activity.

Eigenvector localization: For ζ<5/2, a delocalized leading eigenvector implies disease spreading over the whole network above the QMF threshold.This corresponds to a finite density of infected individuals.
Eigenvector localization: For ζ>5/2, localization confines activity to hubs and their neighbors, producing infected-node counts that scale sublinearly with system size.The review states that this does not constitute a true active state.
Hub activation: When hubs are directly connected, sufficiently long node lifetimes allow mutual reinfection and an endemic state above the QMF critical point.The mechanism depends on hub connectivity and spreading-rate-dependent lifetimes.
Hub activation: When hubs are not directly connected, the review associates activity above the QMF threshold with a Griffiths phase and places the true transition at a higher spreading rate.In this phase, infected density decays more slowly than exponentially.
Alternative critical-point criteria: Other reviewed work reports a vanishing critical point for small-world networks with degree distributions decaying slower than exponentially, including power-law networks with any ζ.This contrasts with interpretations predicting a finite threshold for ζ>3.

13. Conclusions

The review organizes theoretical and computational approaches for spreading processes on single- and multilayer networks, linking formalisms to appropriate simulations and assessing selected approximations.

Scope and classification: Spreading processes are classified by time treatment into continuous-time and cellular-automata approaches, with the latter divided into synchronous and asynchronous schemes.The review emphasizes distinguishing these approaches properly.
Theoretical framework: The review presents MF, HMF, QMF, and PQMF methods and relates PQMF to non-backtracking matrices and message passing.The authors identify this relationship as absent from previous literature to their knowledge.
Simulation methods: It discusses simulation procedures for continuous-time and cellular-automata models and the correct association between mathematical frameworks and algorithms.The review also analyzes QMF and PQMF accuracy against Monte Carlo simulations.
Purpose: The review primarily aims to clarify formalisms and their main ideas rather than provide an extensive literature review.Its intended use is to help readers handle different specific situations.

Appendix A.

Appendix A summarizes mean-field approximations and their numerical treatment for SIS, SIR, and MT processes, with assumptions and solution approaches stated for the reviewed network settings.

Summary tables: Tables A.3 and A.4 summarize the mean-field approximations and corresponding numerical approximations for SIS, SIR, and MT processes.The appendix focuses on the approximations and how they are solved numerically.
Assumptions: The appendix focuses on uncorrelated networks and assumes dynamical correlations are negligible, while noting that each mean-field approach makes a different approximation.For HMF on uncorrelated networks, it specifies P(k′|k)=k′P(k′)/⟨k⟩.
Numerical treatment: Numerical methods such as Runge–Kutta can solve the approximation equations, and QMF and PQMF are compared with Monte Carlo results.Figure 13 is cited as an example of this comparison.
Approximation meanings: The appendix distinguishes QMF, formulated on a fixed network, from HMF, which treats nodes of a given degree as statistically equivalent.The listed threshold expressions are presented for finite networks, with thresholds tending to zero in the thermodynamic limit in the stated scale-free setting.
Reference material: The appendix includes compact reference tables for the reviewed approximation equations and associated spreading processes.These tables are intended as a consolidated reference for the methods discussed in the review.