Rare-event sampling for stochastic dynamics in network systems using cluster updates

Conditional-path Monte Carlo for rare stochastic dynamics on networks: Details and derivations

This paper provides the rigorous mathematical foundations and algorithmic details underlying the CPMC framework, and details a dynamic programming scheme to exactly implement complex boundary conditions - including patient-zero and macroscopic outbreak-size constraints - enabling the rejection-free generation of valid trajectories.

Extreme outbreaks in non-Markovian epidemics on complex networks

Extreme epidemic risk is controlled by the right tail of the outbreak-size distribution, but this distribution is generally unknown for non-Markovian spreading on networks. Here we determine this distribution by mapping non-Markovian SIR dynamics to an effective Markovian description. We show that arbitrary infection and recovery time statistics can be incorporated through a single edge transmissibility, yielding an effective Markovian process that reproduces the full outbreak-size statistics. For weakly heterogeneous networks, the reduction yields a universal well-mixed semiclassical theory governed by the bond-percolation reproductive number. Outbreak statistics across diverse waiting-time distributions and topologies collapse onto one predictive curve. For highly heterogeneous and empirical networks, the corresponding effective Markovian dynamics on the network captures the complete distribution. Our results provide a direct route from measured waiting-time distributions to quantitative predictions of network-level extreme-outbreak risk.

Simulation and inference methods for non-Markovian stochastic reaction networks.

Stochastic models of reaction networks are widely used to capture intrinsic noise in complex systems in the life sciences. Typical formulations of these models are based on Markov processes for which there is extensive research on efficient simulation and inference. However, there are complex processes in biology, such as gene transcription and translation, that introduce history dependent dynamics requiring non-Markovian processes to accurately capture the stochastic dynamics of the system. This greater realism comes with additional computational challenges for simulation and parameter inference. We develop efficient stochastic simulation algorithms for well-mixed non-Markovian stochastic reaction networks with stochastic delays that depend on system state and time. Our methods generalize the next reaction method and τ-leaping method to support arbitrary inter-event time distributions while preserving computational scalability. We also introduce a coupling scheme to generate exact non-Markovian sample paths that are positively correlated to an approximate non-Markovian τ-leaping sample path. This enables substantial computational gains for simulation and Bayesian inference through multilevel Monte Carlo and multifidelity schemes. We demonstrate the effectiveness of our approach using several non-Markovian examples, showing substantial gains in both simulation accuracy and inference efficiency. These results extend the practical applicability of non-Markovian models in systems biology and beyond.

Extreme Reachability of Continuous Time Random Walks on Networks

A unified short-time framework for extreme reachability of continuous-time random walks on networks is developed, showing that both the many-walker limit and the frequent-resetting limit are controlled by the short-time asymptotics of the first-passage time distribution, determined by the network's shortest-path structure and transition rates.

Markovian Dynamics and Spectral Relaxation of Metastatic Networks

Exact Bayesian Tracking of Dynamic Network Topologies

Tracking the temporal evolution of network topologies is a fundamental challenge in social networks, epidemiology, and sensor systems, among others. This paper develops an exact Bayesian tracker for unweighted, directed graphs using nodal signal observations. This framework yields the full posterior probability distribution over network states at each time step, naturally enabling uncertainty quantification, prediction, and principled decision-making. We model the network dynamics as a Markov process on the Boolean hypercube, where edges transition independently according to a flip probability. For efficient computation, we cast the prediction step as a dyadic convolution, and leverage the Fast Walsh-Hadamard Transform to reduce the computational cost from $\mathcal{O} (4^k)$ to $\mathcal{O} (k 2^k)$, where $k$ is the maximum node degree. When the network transition probabilities are unknown, we develop an Expectation-Maximization framework to learn them from the observed signals. Comprehensive experiments on synthetic and six real-world datasets validate the proposed method and demonstrate its superior tracking accuracy, faster recovery from topological changes, and meaningful uncertainty estimates compared to state-of-the-art and classical baselines.