Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 3585-3596· 0 citations· 32 references
Abstract
Extreme events play a central role in networked stochastic processes, governing the fastest information spreading, quickest search, and earliest arrival in many real-world systems. In this paper, we develop a unified short-time framework for extreme reachability of continuous-time random walks on networks. We show that both the many-walker limit and the frequent-resetting limit are controlled by the short-time asymptotics of the first-passage time distribution, which is determined by the network's shortest-path structure and transition rates. By introducing an instantaneous arrival intensity based on shortest-path contributions, we derive explicit scaling laws for extreme first-passage times and demonstrate that these seemingly distinct regimes are governed by the same underlying network quantity. Our framework reveals a universal mechanism by which network topology shapes extreme events in continuous-time dynamics, independent of long-time diffusion properties. We further propose an efficient method to compute the short-time arrival intensity on large networks and validate our predictions on both synthetic and real-world graphs. The results provide a principled basis for quantifying extreme reachability, fastest search, and robustness under restarting in networked systems.
A novel technique called conditional-path Monte Carlo (CPMC), inspired by loop algorithms from equilibrium condensed-matter physics, which generates a Markov chain of trajectories that all strictly respect the targeted macroscopic boundary conditions like the occurrence of a massive network failure.
Jiazheng Sun, James Moody, Thomas Barthel· 1 citation
Piecewise diffusion Markov processes (PDifMPs) are valuable for modelling systems where continuous dynamics are interrupted by sudden shifts and/or changes in drift and diffusion. The first-passage time (FPT) in such models plays a central role in understanding when a process first reaches a critical boundary. In many systems, time-dependent thresholds provide a flexible framework for reflecting evolving conditions, making them essential for realistic modelling. We propose a hybrid asymptotically exact simulation scheme for computing the FPT of PDifMPs to time-dependent thresholds. Exact methods traditionally exist for pure diffusions, using Brownian motion as an auxiliary process and accepting sampled paths with a probability weight. Between jumps, the PDifMP evolves as a diffusion, allowing us to apply the exact method within each inter-jump interval. The main challenge arises when no threshold crossing is detected over an interval: we then need the value of the process at the jump time, and to that end, we introduce an approach to simulate a conditionally constrained auxiliary process and derive the corresponding acceptance probability. Furthermore, we prove the convergence of the method and illustrate it using numerical examples.
Sascha Desmettre, Devika Khurana, A. Meddah· Journal of Scientific Comput...· 0 citations
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.
Thomas Barthel, Jiazheng Sun, Jhao-Hong Peng· 1 citation
We investigate the persistence of most probable paths through the Onsager--Machlup functional for multidimensional stochastic differential equations driven by fractional Brownian motion with time-dependent diffusion coefficients and Hurst parameter $H\in(1/4,1)$. Under suitable structural and variational conditions, deterministic trajectories remain most probable paths for sufficiently small noise in both the fixed-endpoint transition problem and the free-endpoint evolution problem, whereas sufficiently large noise destroys their local minimality. More generally, when exact persistence does not hold, global most probable paths converge to the corresponding trajectories of the noise-free system in both the uniform and H\"older topologies at the rate $O(\epsilon)$. We further analyze the second variation along periodic deterministic trajectories over time intervals of length $NT$. For $H>1/2$, positive definiteness, and hence local minimality, is lost on sufficiently long intervals. For $H\in(1/4,1/2]$, long-time positive definiteness holds for the fixed-endpoint problem, but this conclusion does not directly extend to the free-endpoint setting. We also establish the persistence of KAM tori in nearly integrable Hamiltonian systems in the sense of most probable evolution paths. Finally, a two-dimensional numerical example illustrates the persistence of deterministic trajectories under small noise and their pronounced deviation under large noise.
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.
Extreme first-passage events are broadly relevant to biological, chemical, and physical processes in which the first successful arrival determines the outcome. Existing theories are confined to noninteracting searchers. Interacting extreme-statistics problems are notoriously difficult because correlations destroy probability factorization. We establish a general framework for interacting extreme search. A no-go theorem shows that broad classes of bounded interactions cannot beat the $1/\ln N$ extreme timescale of $N$ independent Brownian searchers, and complementary upper bounds prove that this scale is exact for broad classes of repulsive interactions. We then identify two sharp mechanisms beyond the logarithmic class and derive a unified interaction-driven acceleration limit. In particular, deterministic pairwise interaction can at most reduce the extreme search time to order $1/N$, while stochastic pairwise forcing attains $1/(N\ln N)$. Our results separate acceleration due to statistical redundancy from that generated by coherent many-body transport or amplified fluctuations, deepening our understanding of interacting stochastic systems.
Ruicheng Bao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
