Source-linked AI summary
Rare-event sampling for stochastic dynamics in network systems using cluster updates
Jiazheng Sun, James Moody, Thomas Barthel
TL;DR
Rare macroscopic events in heterogeneous networks are difficult to study because standard forward-time simulation rejects most paths and existing rare-event methods face additional sampling problems. The paper introduces conditional-path Monte Carlo, using rejection-free non-local spacetime-cluster updates and dynamic programming to generate constrained trajectories. In SIS outbreaks on kinship networks, every CPMC sample satisfies the prescribed constraint, providing direct access to rare-event trajectories.
Problem
Rare events in heterogeneous networks are difficult to investigate because forward-time simulation discards most paths, while existing rare-event methods face sampling challenges such as trapping and degeneracy.
Method
CPMC uses rejection-free non-local spacetime-cluster updates and dynamic programming to generate Markov-chain trajectories that satisfy macroscopic constraints.
Results
Every CPMC sample satisfies the prescribed constraint, whereas targeted large outbreaks at α = 0.6 occur with probability of order 10^-3 in the SIS case study.
Takeaways & Limitations
CPMC provides direct access to rare-event trajectories for stochastic dynamics on complex networks while avoiding vanishing acceptance rates of traditional forward-time simulation.
Takeaways & Limitations
Small deviations were attributed to limited samples, lock avalanches, and boundary-enforced conditional state-locks that slightly break detailed balance.
Abstract
from arXiv · showhide
Understanding the stochastic evolution in complex networks is a central challenge across physics, biology, engineering, social science, and finance. The most consequential macroscopic events, like cascading failures in communication networks, widespread epidemic outbreaks, and rapid shifts in societal opinions, often emerge from a confluence of rare, localized stochastic processes and need to pass certain bottlenecks. Standard forward-time simulation algorithms like the Gillespie method are inefficient for the investigation of such phenomena due to catastrophic rejection rates. Advanced rare-event techniques like splitting methods and transition-path sampling often suffer from kinetic trapping, path degeneracy, genealogical correlations, or critical slowing down when applied to complex heterogeneous networks. We propose to overcome this challenge by establishing a novel technique called conditional-path Monte Carlo (CPMC), inspired by loop algorithms from equilibrium condensed-matter physics. By employing non-local updates on spacetime clusters without rejections, CPMC generates a Markov chain of trajectories that all strictly respect the targeted macroscopic boundary conditions like the occurrence of a massive network failure. We demonstrate the framework's potential by performing a simple risk factor analysis for rare large-scale epidemic outbreaks in SIS dynamics on kinship networks.
Introduction.
Rare macroscopic events in heterogeneous networks arise from localized stochastic processes that must pass structural bottlenecks, but standard simulation and existing rare-event methods struggle to sample them efficiently. The paper introduces CPMC, which uses rejection-free, non-local spacetime-cluster updates to generate trajectories satisfying target constraints.
- Motivation: Rare network events such as failures, epidemics, and opinion shifts arise from improbable combinations of local processes and heterogeneous-network bottlenecks.Risk analysis and intervention design therefore require dynamics conditioned on rare macroscopic outcomes.
- Limitations of existing models: Classical compartmental models often miss rare macroscopic events because they assume homogeneous mixing and neglect dynamical stochasticity.Their coarse-grained expectations wash out network heterogeneity relevant to rare-event emergence.
- Limitations of existing methods: Most forward-time stochastic simulation paths fail to realize targeted rare events and are discarded, producing catastrophic rejection rates.In epidemic dynamics, most disease surges fade quickly while only a small fraction reaches a macroscopic network fraction.
- Limitations of existing methods: Existing rare-event techniques face weight degeneracy, kinetic trapping, path degeneracy, genealogical correlations, or critical slowing down on complex networks.These challenges affect importance sampling, splitting methods, and local path-update approaches.
- Proposed approach: CPMC updates entire trajectories through connected spacetime clusters, generating a Markov chain whose trajectories strictly satisfy prescribed macroscopic constraints.The method is inspired by loop algorithms and uses Swendsen-Wang-like non-local updates without rejection.
- Illustrative case study: A rural Indian contact-network case study contains 519 nodes, with most simulated outbreaks affecting fewer than five households and rare outbreaks exceeding 20%.The simulations use an SIR model with infection probability 0.015 and a fixed recovery time of 13 rounds.
Conditional-path Monte Carlo.
Conditional-path Monte Carlo samples constrained stochastic trajectories through non-local spacetime cluster updates rather than rejecting forward-time paths. Applied to SIS dynamics, it constructs compatible graph configurations, updates free clusters, and supports constrained outbreak sampling and risk-factor analysis.
- Motivation: CPMC targets trajectories satisfying macroscopic constraints C(σ), avoiding the catastrophic rejection produced when forward-time SSA generates mostly invalid paths.The constraints can specify initial conditions and outbreak-size thresholds.
- Core method: CPMC generates a Markov chain through non-local spatiotemporal cluster updates that strictly preserve the desired trajectory constraints.The update proceeds through an intermediate graph configuration before changing cluster states.
- Core method: The intermediate graph decomposes the full spacetime volume into connected clusters, with free clusters allowing multiple base states mapped to physical node states.Graph vertices encode state-changing or possible events and impose local state relations or restrictions.
- Cluster updates: Free-cluster states are sampled simultaneously across entire spacetime clusters, enabling substantial changes to infection trajectories while maintaining compatible dynamics.The SIS example shows changes to both the trunk and leaves of the infection tree after cluster flips.
- Constrained sampling: Dynamic programming samples free-cluster states that satisfy exactly one patient zero and a minimum final outbreak size, with complexity O(KNfree).A forward table counts valid initial and final infection totals, followed by backward sampling of cluster states.
SIS outbreaks in kinship networks.
CPMC is applied to rare large SIS outbreaks on heterogeneous kinship networks, enabling conditional sampling and risk-factor analysis. Its outbreak trajectories agree with Gillespie simulations, while revealing higher initiation risk for more central nodes and a broader vulnerable group.
- Conditional outbreak sampling: CPMC simulates rare SIS outbreaks under prescribed boundary constraints, with every sampled trajectory satisfying the constraint without rejection.The analysis uses a single patient zero and a large-outbreak threshold on kinship networks.
- Risk-factor analysis: Large outbreaks originate preferentially from a few central nodes, whereas the group vulnerable to infection is considerably broader.This heterogeneity is reported for the small kinship network and motivates node-level risk analysis.
- Risk-factor analysis: Patient-zero probability rises sharply around 110% of the average centrality ⟨c_i⟩ = 0.065.The result links outbreak initiation risk to structural centrality.
- Validation: At α = 0.6, conditional mean infection counts from CPMC and Gillespie simulations agree well over the entire time interval.The validation is performed on the 8623-node network B.
- Validation: Small deviations near t = 11 and t = 20 are attributed to limited samples, lock avalanches, and conditional state-locks that slightly break detailed balance.The employed edge vertex set E1 increases autocorrelations; parallel tempering mitigated them in this validation.
- Validation: At α = 0.6, targeted outbreaks occur with probability of order 10^-3, requiring hundreds of discarded Gillespie samples per accepted outbreak trajectory.The outbreak probability decreases exponentially as α decreases, whereas every CPMC sample satisfies the constraint.
Conclusion.
CPMC is presented as a rejection-free rare-event framework that updates entire trajectory spacetime clusters while maintaining targeted macroscopic constraints. The conclusion highlights its potential for identifying risk factors in catastrophic events, while noting several directions requiring further methodological development.
- CPMC applies rejection-free, non-local spacetime-cluster updates and dynamic programming to generate trajectories satisfying targeted macroscopic constraints.
- The framework is positioned to address large heterogeneous networks, rigid topological bottlenecks, and complex boundary conditions.
- The SIS kinship-network demonstration suggests that CPMC can support efficient identification of critical risk factors for catastrophic events.The paper connects this capability to rare phenomena across physics, biology, engineering, social science, and finance.
- Further CPMC details, derivations, and comparisons with exact solutions on small networks are deferred to a technical companion paper.
- Future work must address lock avalanches, implementation details for temporal networks and time-dependent rates, autocorrelation reduction, and scalability through parallel tempering or adaptive machine learning.