Dynamic message-passing equations for models with unidirectional dynamics

Learning of networked spreading models from noisy and incomplete data

Recent years have seen a lot of progress in algorithms for learning parameters of spreading dynamics from both full and partial data. Some of the remaining challenges include model selection under the scenarios of unknown network structure, noisy data, missing observations in time, as well as an efficient incorporation of prior information to minimize the number of samples required for an accurate learning. Here, we introduce a universal learning method based on a scalable dynamic message-passing technique that addresses these challenges often encountered in real data. The algorithm leverages available prior knowledge on the model and on the data, and reconstructs both network structure and parameters of a spreading model. We show that a linear computational complexity of the method with the key model parameters makes the algorithm scalable to large network instances.

Dynamical phase transitions in graph cellular automata

Discrete dynamical systems can exhibit complex behavior from the iterative application of straightforward local rules. A famous class of examples comes from cellular automata whose global dynamics are notoriously challenging to analyze. To address this, we relax the regular connectivity grid of cellular automata to a random graph, which gives the class of graph cellular automata. Using the dynamical cavity method and its backtracking version, we show that this relaxation allows us to derive asymptotically exact analytical results on the global dynamics of these systems on sparse random graphs. Concretely, we showcase the results on a specific subclass of graph cellular automata with "conforming nonconformist" update rules, which exhibit dynamics akin to opinion formation. Such rules update a node's state according to the majority within their own neighborhood. In cases where the majority leads only by a small margin over the minority, nodes may exhibit nonconformist behavior. Instead of following the majority, they either maintain their own state, switch it, or follow the minority. For configurations with different initial biases towards one state we identify sharp dynamical phase transitions in terms of the convergence speed and attractor types. From the perspective of opinion dynamics this answers when consensus will emerge and when two opinions coexist almost indefinitely.

Heterogeneous message passing for heterogeneous networks

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

Ensemble inference of unobserved infections in networks using partial observations

Undetected infections fuel the dissemination of many infectious agents. However, identification of unobserved infectious individuals remains challenging due to limited observations of infections and imperfect knowledge of key transmission parameters. Here, we use an ensemble Bayesian inference method to infer unobserved infections using partial observations. The ensemble inference method can represent uncertainty in model parameters and update model states using all ensemble members collectively. We perform extensive experiments in both model-generated and real-world networks in which individuals have differential but unknown transmission rates. The ensemble method outperforms several alternative approaches for a variety of network structures and observation rates, despite that the model is mis-specified. Additionally, the computational complexity of this algorithm scales almost linearly with the number of nodes in the network and the number of observations, respectively, exhibiting the potential to apply to large-scale networks. The inference method may support decision-making under uncertainty and be adapted for use for other dynamical models in networks.

Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions

The dynamic cavity method provides the most efficient way to evaluate probabilities of dynamic trajectories in systems of stochastic units with unidirectional sparse interactions. It is closely related to sum-product algorithms widely used to compute marginal functions from complicated global functions of many variables, with applications in disordered systems, combinatorial optimization, and computer science. However, the complexity of the cavity approach grows exponentially with the in-degrees of the interacting units, which creates a defacto barrier for the successful analysis of systems with fat-tailed in-degree distributions. In this paper, we present a dynamic programming algorithm that overcomes this barrier by reducing the computational complexity in the in-degrees from exponential to quadratic, whenever couplings are chosen randomly from (or can be approximated in terms of) discrete, possibly unit-dependent, sets of equidistant values. As a case study, we analyze the dynamics of a random Boolean network with a fat-tailed degree distribution and fully asymmetric binary ±J couplings, and we use the power of the algorithm to unlock the noise-dependent heterogeneity of stationary node activation patterns in such a system.

Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis

Infectious diseases that incorporate presymptomatic transmission are challenging to monitor, model, predict, and contain. We address this scenario by studying a variant of a stochastic susceptible-exposed-infected-recovered model on arbitrary network instances using an analytical framework based on the method of dynamic message passing. This framework provides a good estimate of the probabilistic evolution of the spread on both static and contact networks, offering a significantly improved accuracy with respect to individual-based mean-field approaches while requiring a much lower computational cost compared to numerical simulations. It facilitates the derivation of epidemic thresholds, which are phase boundaries separating parameter regimes where infections can be effectively contained from those where they cannot. These have clear implications on different containment strategies through topological (reducing contacts) and infection parameter changes (e.g., social distancing and wearing face masks), with relevance to the recent COVID-19 pandemic.

Suppression of epidemic spreading process on multiplex networks via active immunization

Spatial epidemic spreading, a fundamental dynamical process upon complex networks, attracts huge research interest during the past few decades. To suppress the spreading of epidemic, a couple of effective methods have been proposed, including node vaccination. Under such a scenario, nodes are immunized passively and fail to reveal the mechanisms of active activity. Here, we suggest one novel model of an observer node, which can identify infection through interacting with infected neighbors and inform the other neighbors for vaccination, on multiplex networks, consisting of epidemic spreading layer and information spreading layer. In detail, the epidemic spreading layer supports susceptible-infected-recovered process, while observer nodes will be selected according to several algorithms derived from percolation theory. Numerical simulation results show that the algorithm based on large degree performs better than random placement, while the algorithm based on nodes' degree in the information spreading layer performs the best (i.e., the best suppression efficacy is guaranteed when placing observer nodes based on nodes' degree in the information spreading layer). With the help of state probability transition equation, the above phenomena can be validated accurately. Our work thus may shed new light into understanding control of empirical epidemic control.

Exact analytical solution of irreversible binary dynamics on networks

In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), and nodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfy a predetermined condition. We introduce a set of recursive equations to compute the probability of reaching any final state, given an initial state, and a specification of the transition probability function of each node. Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, we also introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves the equations as efficiently as possible in exponential time.

Matrix product algorithm for stochastic dynamics on networks applied to nonequilibrium Glauber dynamics

We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

Optimal deployment of resources for maximizing impact in spreading processes

The effective use of limited resources for controlling spreading processes on networks is of prime significance in diverse contexts, ranging from the identification of "influential spreaders" for maximizing information dissemination and targeted interventions in regulatory networks, to the development of mitigation policies for infectious diseases and financial contagion in economic systems. Solutions for these optimization tasks that are based purely on topological arguments are not fully satisfactory; in realistic settings, the problem is often characterized by heterogeneous interactions and requires interventions in a dynamic fashion over a finite time window via a restricted set of controllable nodes. The optimal distribution of available resources hence results from an interplay between network topology and spreading dynamics. We show how these problems can be addressed as particular instances of a universal analytical framework based on a scalable dynamic message-passing approach and demonstrate the efficacy of the method on a variety of real-world examples.

Spreading dynamics of forget-remember mechanism

We study extensively the forget-remember mechanism (FRM) for message spreading, originally introduced in Eur. Phys. J. B 62, 247 (2008)EPJBFY1434-602810.1140/epjb/e2008-00139-4. The freedom of specifying forget-remember functions governing the FRM can enrich the spreading dynamics to a very large extent. The master equation is derived for describing the FRM dynamics. By applying the mean field techniques, we have shown how the steady states can be reached under certain conditions, which agrees well with the Monte Carlo simulations. The distributions of forget and remember times can be explicitly given when the forget-remember functions take linear or exponential forms, which might shed some light on understanding the temporal nature of diseases like flu. For time-dependent FRM there is an epidemic threshold related to the FRM parameters. We have proven that the mean field critical transmissibility for the SIS model and the critical transmissibility for the SIR model are the lower and the the upper bounds of the critical transmissibility for the FRM model, respectively.

Recovery rate affects the effective epidemic threshold with synchronous updating

Accurate identification of effective epidemic threshold is essential for understanding epidemic dynamics on complex networks. In this paper, we systematically study how the recovery rate affects the susceptible-infected-removed spreading dynamics on complex networks, where synchronous and asynchronous updating processes are taken into account. We derive the theoretical effective epidemic threshold and final outbreak size based on the edge-based compartmental theory. To validate the proposed theoretical predictions, extensive numerical experiments are implemented by using asynchronous and synchronous updating methods. When asynchronous updating method is used in simulations, recovery rate does not affect the final state of spreading dynamics. But with synchronous updating, we find that the effective epidemic threshold decreases with recovery rate, and final outbreak size increases with recovery rate. A good agreement between the theoretical predictions and the numerical results are observed on both synthetic and real-world networks. Our results extend the existing theoretical studies and help us to understand the phase transition with arbitrary recovery rate.

Predicting the epidemic threshold of the susceptible-infected-recovered model

Researchers have developed several theoretical methods for predicting epidemic thresholds, including the mean-field like (MFL) method, the quenched mean-field (QMF) method, and the dynamical message passing (DMP) method. When these methods are applied to predict epidemic threshold they often produce differing results and their relative levels of accuracy are still unknown. We systematically analyze these two issues-relationships among differing results and levels of accuracy-by studying the susceptible-infected-recovered (SIR) model on uncorrelated configuration networks and a group of 56 real-world networks. In uncorrelated configuration networks the MFL and DMP methods yield identical predictions that are larger and more accurate than the prediction generated by the QMF method. As for the 56 real-world networks, the epidemic threshold obtained by the DMP method is more likely to reach the accurate epidemic threshold because it incorporates full network topology information and some dynamical correlations. We find that in most of the networks with positive degree-degree correlations, an eigenvector localized on the high k-core nodes, or a high level of clustering, the epidemic threshold predicted by the MFL method, which uses the degree distribution as the only input information, performs better than the other two methods.

Message-passing approach for recurrent-state epidemic models on networks

Epidemic processes are common out-of-equilibrium phenomena of broad interdisciplinary interest. Recently, dynamic message-passing (DMP) has been proposed as an efficient algorithm for simulating epidemic models on networks, and in particular for estimating the probability that a given node will become infectious at a particular time. To date, DMP has been applied exclusively to models with one-way state changes, as opposed to models like SIS and SIRS where nodes can return to previously inhabited states. Because many real-world epidemics can exhibit such recurrent dynamics, we propose a DMP algorithm for complex, recurrent epidemic models on networks. Our approach takes correlations between neighboring nodes into account while preventing causal signals from backtracking to their immediate source, and thus avoids "echo chamber effects" where a pair of adjacent nodes each amplify the probability that the other is infectious. We demonstrate that this approach well approximates results obtained from Monte Carlo simulation and that its accuracy is often superior to the pair approximation (which also takes second-order correlations into account). Moreover, our approach is more computationally efficient than the pair approximation, especially for complex epidemic models: the number of variables in our DMP approach grows as 2mk where m is the number of edges and k is the number of states, as opposed to mk^{2} for the pair approximation. We suspect that the resulting reduction in computational effort, as well as the conceptual simplicity of DMP, will make it a useful tool in epidemic modeling, especially for high-dimensional inference tasks.

Dynamic message-passing approach for kinetic spin models with reversible dynamics

A method to approximately close the dynamic cavity equations for synchronous reversible dynamics on a locally treelike topology is presented. The method builds on (a) a graph expansion to eliminate loops from the normalizations of each step in the dynamics and (b) an assumption that a set of auxilary probability distributions on histories of pairs of spins mainly have dependencies that are local in time. The closure is then effectuated by projecting these probability distributions on n-step Markov processes. The method is shown in detail on the level of ordinary Markov processes (n=1) and outlined for higher-order approximations (n>1). Numerical validations of the technique are provided for the reconstruction of the transient and equilibrium dynamics of the kinetic Ising model on a random graph with arbitrary connectivity symmetry.