CS Paper Radar

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

Thomas Barthel, Jiazheng Sun, Jhao-Hong Peng

cs.SI cond-mat.stat-mechphysics.comp-phphysics.soc-ph ·submitted 2026-08-18 08:36 UTC · v1

Abstract

The simulation of rare macroscopic events in stochastic network dynamics, such as widespread epidemic outbreaks, cascading failures in communication networks, or the escape from metastable states in many-body systems, is severely hindered by methodological challenges like catastrophic rejection rates, weight degeneracy, genealogical correlations, and critical slowing down inherent to standard forward-time algorithms, splitting methods, and transition-path sampling. Conditional-path Monte Carlo (CPMC) overcomes these limitations by employing non-local Swendsen-Wang-like cluster updates that operate directly on full-system trajectories. Serving as the technical companion to [Sun, Moody, and Barthel, arXiv:2608.16171], this paper provides the rigorous mathematical foundations and algorithmic details underlying the CPMC framework. We formally define the joint path-graph probability weights and derive the transition and uniformization sum rules that guarantee detailed balance. Applying the framework to susceptible-infectious-susceptible (SIS) models, we systematically construct and optimize single-node and edge graph vertex sets specifically designed to prevent lock avalanches and maintain the structural mobility of the epidemic trunk. Furthermore, we detail 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. Finally, we assess the computational complexity of the algorithm, describe parallelization strategies, and validate CPMC against exact solutions for dynamics on small networks.

Comment
16+2 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.SI cond-mat.stat-mechphysics.comp-phphysics.soc-ph ·2026-08-17 ·Jiazheng Sun, James Moody, Thomas Barthel
similarity 0.83
Abstract · 5 pages, 4 figures

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.

0.56

Multiplicative Path Weights in Networks: From Katz Connectivity to Mean First-Passage Times

cs.SI math.PRphysics.soc-ph ·2026-10-15 ·Robbert van der Burg, Bernd Heidergott, Thao Le, Alessandro Zocca
similarity 0.65
Abstract

Signal dispersion, stress propagation in interbank systems, and transmission probabilities in epidemic and reliability models are all captured by studying paths on directed graphs where the path weight is defined as the product of its edge weights. Connectivity in such networks is naturally quantified by aggregating these multiplicative path weights across nodes. This paper provides a comprehensive treatise on connectivity and ranking measures based on multiplicative path weights. We demonstrate how standard all-path connectivity, such as the standard Katz centrality, can be extended beyond its classical spectral threshold. In addition, we derive closed-form expressions for connectivity based on first-hit paths and introduce a new version of Katz centrality. Furthermore, for random edge weights, we derive resolvent-based expressions for the first and second moments, alongside variance bounds, under a path-indexed coupling framework. Finite irreducible Markov chains are a subclass of the models studied, and we show that the scaled matrix of first-hit path probabilities is the probability-generating function for first-passage and return times, and that differentiation yields the classical first-passage times. Numerical examples illustrate the application of our results in a variety of settings.

0.23

Local Reproduction Numbers for Analysis and Optimal Mitigation of Epidemic Processes

eess.SY ·2026-10-06 ·José I. Caiza, Junjie Qin, Philip E. Paré
similarity 0.65
Abstract

In this paper, we propose a unifying framework to analyze layered networked epidemic processes where the population, represented either as a networked SIS or SIR model, is coupled with an infrastructure network. We propose novel local metrics that enable the analysis of the epidemic spreading locally (node-level) and the prediction of the network-wide spreading under some sufficient conditions. Inspired by the bilayer nature of our model, we partition the layered network between intra- and inter-layer interactions. We identify conditions at the layer level which allow the characterization of the network-level basic reproduction number in terms of the physical structure of the layered network. Then, we leverage the local metrics to propose an optimization framework for epidemic mitigation based on a fundamental notion: the network-wide spreading can be quantified by the aggregation of the local (node-level) epidemic burden. We provide guarantees that the local metric-based optimization can be solved as a geometric program. We illustrate our theoretical results via numerical examples and evaluate the performance of the local metrics and the optimization framework they enable versus other existing epidemic mitigation approaches based on network-level metrics.

0.21

Fast and Scalable Influence Estimation in the Independent Cascade Model: a unified framework

cs.SI ·2026-10-23 ·Matic Požar, Miklós Krész
benchmark similarity 0.65
Abstract

Computing diffusion processes on networks is fundamental to applications including influence maximization, epidemic modeling, information propagation, and diffusion inference. The Independent Cascade (IC) model is one of the most widely used models of progressive diffusion, yet exact computation of its activation probabilities is #P-hard, while Monte Carlo simulation becomes costly when accurate estimates are required repeatedly. Despite its central role, analytical approximation of the IC diffusion function has received comparatively little systematic attention relative to the extensive literature on influence-maximization algorithms. We present a comprehensive study of analytical approximations for the IC model. We review a wide range of existing approaches and unify them through a common framework based on temporal representation, retained propagation information, and aggregation rule. This perspective exposes connections between previously distinct approximation families and motivates several new methods. We further conduct, to our knowledge, the first large-scale cross-family comparison of analytical IC approximations for node-level marginal activation probabilities. Our benchmark spans real-world and synthetic networks with systematically varied topology, seed-set size, edge-probability model, and diffusion strength. The proposed second-order dynamic message-passing method achieves the lowest pooled median error and the lowest dataset- or graph-family-level median error on every network considered. The results reveal systematic differences between approximation families, identify regimes in which higher-order corrections are most beneficial, and establish analytical IC approximation as a rich accuracy-efficiency design space rather than a collection of isolated methods.

0.15

A Novel Approach for the SDIR Epidemic Model on Online Social Networks

cs.SI cs.NImath.OC ·2026-09-27 ·Nguyen Hong Phuc, Duong Khanh Ly, Hoang Phi Dung
theory similarity 0.62
Abstract · Welcome comments

Information diffusion can be controlled by restricting or removing links (edges) in online social networks, as well as in real-world networks. To identify the most influential links to remove while minimizing diffusion, previous studies have proposed upper bounds for spreading processes in SIR and SIS models, using supermodularity and weighted matrices to identify critical links in contact networks. However, in some cases, existing upper bounds are not sufficiently tight to accurately capture the effect of important edges, as in the SDIR model of [14] (Khanh-Cho-Dung, Proceedings of 40th ICOIN, 2026). We therefore propose a tighter upper bound for controlling diffusion in the SDIR model by directly analyzing the dynamics of the two state vectors D and I in a $2N$-dimensional space. This approach yields an improved spectral-radius convergence condition and outperforms the previous method. Simulations on the synthetic Erdos-Renyi network and the real-world Haslemere dataset using a Greedy edge-deletion algorithm demonstrate its effectiveness for influence minimization on social networks.

0.18

Percolation in the Stochastic Block Model

cs.SI physics.soc-phcond-mat.stat-mechmath.PR ·2026-09-22 ·Luca Pieleanu, Moritz Laber, Narayan G. Sabhahit, Dmitri Krioukov
similarity 0.62
Abstract · 23 pages, 10 figures

The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.

0.19

Fundamental limits to identifying node and tie memory in temporal networks: marginal artefacts and spreading dynamics

cs.SI physics.soc-ph ·2026-09-09 ·Michele Tizzani
published similarity 0.61
Abstract · 24 pages, 8 figures; 43 pages Supplementary Material

Temporal-network models place the memory seen in contact data either on nodes, through self-excitation (branching ratio n_node), or on ties, through reinforcement (kappa). The two choices reproduce the same coarse statistics but predict different epidemics. We ask whether contact data can tell them apart and find two limits. The first is attribution. When the initiator of every event is recorded, the likelihood factorises into a timing block containing n_node and a selection block containing kappa, so the two are estimated independently. When it is not, as in proximity data, a missing-information term couples them, with a size set by the entropy of the initiator posterior. The second issue is interpretation. Even where the mechanisms separate, the fitted n_node might not accurately measure memory and it may be set by the distribution of waiting times between events. Shuffling each node's inter-event order, which keeps that distribution, typically changes the estimated n_node by less than 10%; this is a bias that longer records and a flexible scale-free kernel do not remove. Whether node memory is present must therefore be decided by model-free statistics, which find only weak order memory in the proximity records, far less than the fitted n_node around 0.9 would imply. Tie reinforcement remains recoverable, although a latent initiator inflates it by 28%-45%. The two limits lead to two recommendations: record who initiates each contact, and test a fitted node memory against shuffled and model-free benchmarks before interpreting it. On a high-school record, simulating from the fitted node memory under-predicts outbreak sizes by up to a factor of 2, whereas keeping tie reinforcement alone is closer at low transmissibility but overshoots at high.

0.38

BaCon: Band-Concentrated Exponential Random Graph Models

cs.SI ·2026-11-03 ·Enrico Schiazzano, Giulia Preti, Aristides Gionis, Matteo Riondato, Gianmarco De Francisci Morales
similarity 0.61
Abstract

Exponential-family random graph models ERGMs provide a parametric interpretable framework for modeling real graphs including the Web and social networks Fitted ERGMs may suffer from degeneracy matching observed graph statistics in expectation does not guarantee that the observed graph and similar ones are highly probable under the fitted distribution We introduce Band-Concentrated ERGMs BaCon a framework that avoids degeneracy by imposing a probabilistic constraint requiring at least $1-δ$ of the distribution probability mass to lie on the set of graphs with statistics within an $\varepsilon$-tolerance band around the observed statistics BaCons maximumentropy distribution still belongs to the exponential family while including a factor checking for inclusion in the tolerance band We derive the exact Metropolis-Hastings acceptance rule for this target and use a practical stochastic approximation procedure with a smoothed band membership during fitting Experiments on social networks across increasingly challenging model specifications show that BaCon substantially increases the probability mass assigned to graphs whose statistics are close to the observed ones while remaining estimable for specifications where standard ERGM estimation fails These results demonstrate that probability mass constraints are a principled way to mitigate degeneracy while retaining the benefits of exponential-family graph models

0.28