CS Paper Radar

Finding Patient Zero in Temporal Contact Networks: A Comparative Study

Nathan Cincera Brack, Martin Sterchi, Lorenz Hilfiker, Abraham Bernstein

cs.SI ·submitted 2026-11-17 18:22 UTC · v1

Abstract

Identifying the source of an epidemic, i.e., the patient zero, in a temporal contact network is important for effective outbreak containment and resource allocation. While several methods have been proposed for this task, they have rarely been evaluated under comparable conditions, and no systematic comparison exists for temporal contact networks. We address this gap with a comparative study of seven major methods, namely Steiner Tree (ST), Individual-Based Approximation (IBA), Dynamic Message Passing (DMP), Monte Carlo Mean-Field (MCMF), Soft Margin Estimator (SME), Backtracking Network (BN, a graph neural network), and Belief Propagation (BP). We unify all methods under a single problem formulation and evaluate them on eight diverse temporal networks. In the main experiment, we compare source detection performance for varying basic reproduction numbers. Three complementary experiments on a subset of networks study (i) learning curves, (ii) partial observability, and (iii) parameter misspecification. We find that BP and BN are the strongest source detectors overall. SME is strong under partial observation but mediocre otherwise. IBA, DMP, and MCMF share a common weakness rooted in their factorized-likelihood assumption, leading to overconfident predictions. We identify scaling these methods to larger networks as the most pressing direction for future work.

Comment
21 pages (18 main text, 3 supplementary), 11 figures, 5 tables. This work has been submitted to the IEEE for possible publication

Closest papers

Nearest neighbours by meaning across the whole index.

A temporal graph dissimilarity measure capturing epidemic spreading behavior

cs.SI cs.LG ·2026-10-12 ·Salvatore Freni, Lorenzo Dall'Amico, Francesca Pistilli, Alain Barrat, Tatiana Tommasi +1 more
similarity 0.61
Abstract

Comparing temporal networks is a challenging problem in network analysis. Commonly adopted methods compare structural properties of temporal graphs and can be highly sensitive to the pre-selected features. However, temporal networks are the support of dynamical processes, and a process may take place in statistically indistinguishable ways on structurally different temporal graphs. In particular, a dissimilarity measure that compares temporal graphs based on how spreading processes unfold on them is highly desirable. In this work, we first define the Time-Shift DTW, a dissimilarity between epidemic curves that accounts for both differences in their shape and temporal shifts. We then introduce Epidemic-Aware Temporal Graph Dissimilarity (EATGD), a deterministic and differentiable dissimilarity between temporal graphs that combines an embedding-based temporal graph distance with a set of topological and temporal features. Its parameters are calibrated using stochastic SIR simulations to maximize the correlation with the Time-Shift DTW, after which graph comparisons require no further epidemic simulations. Using empirical human proximity networks from the SocioPatterns collaboration and synthetic temporal graphs, we show that EATGD captures epidemic-based graph dissimilarity and generalizes across heterogeneous network settings. Its differentiability and computational efficiency make EATGD suitable for integration into machine-learning pipelines and provide a potential loss function for training generative models to reproduce epidemic dynamics without requiring an exact reconstruction of fine-grained network structure.

0.19

Gated Graph Neural Networks for Learning Hidden Independent Cascade Dynamics

cs.SI cs.LG ·2026-10-02 ·Anubha Goel, Illia Oleksiienko, Mateusz Wilinski, Alexandros Iosifidis, Juho Kanniainen
benchmark similarity 0.61
Abstract

Information and infectious diseases spread through social networks, but the spreading probabilities driving them are hard to estimate without per-node activation times. Applications seldom supply these, and inference must instead proceed through indirect and noisy proxies for the terminal infection states. We study this inverse problem on a fixed, known graph under the Hidden Independent Cascade (HIC) model, with one spreading probability per node rather than a single global rate, so the number of unknowns scales with the number of nodes. Seed sets and observation parameters are known, while activation times and terminal infection states are latent, and the observed-data likelihood requires marginalizing over every spreading outcome. We propose a simulation-based amortized estimator that recovers the full node-level parameter vector without reconstructing individual latent cascades. Repeated seed-conditioned symptom observations are summarized as Symptom-Aware Cascade Features (SACF), which combine empirical symptom statistics with neighborhood and structural information. SACF are mapped to parameters by SAGE-HC, a permutation-equivariant gated graph neural network whose learned gates attenuate neighborhood messages corrupted by false positives and false negatives, and training on simulated HIC realizations yields a reusable inverse map. As a benchmark under the same hidden observations, we extend the Dynamic Message Passing learning framework to the HIC emission model. On synthetic and empirical graphs the two methods separate by topology. DMP is highly accurate on trees, whereas SAGE-HC is substantially better on heterogeneous, loopy graphs under noisy terminal symptoms.

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.60
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

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

cs.SI cond-mat.stat-mechphysics.comp-phphysics.soc-ph ·2026-08-18 ·Thomas Barthel, Jiazheng Sun, Jhao-Hong Peng
similarity 0.59
Abstract · 16+2 pages, 5 figures

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.

0.42

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.59
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

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.59
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

Target-Aware Network Dismantling with Limited Budgets

cs.SI ·2026-10-06 ·Jiaqi Song, Fei Jing, Wenjie Huang, Xingqin Qi, Qingpeng Zhang
similarity 0.57
Abstract

During epidemics, limited resources dictate critical decisions about whom to isolate or monitor. Conventional public health strategies intuitively prioritize known infected individuals and their immediate contacts. Here, we reveal that this contact-centric approach is fundamentally suboptimal under realistic resource constraints. By formulating this challenge as target-aware network dismantling, we uncover a counter-intuitive, budget-dependent intervention transition. Generating-function analysis demonstrates that when intervention budgets are scarce, isolating structurally central individuals, rather than the immediate neighbours of the infected, protects a vastly larger population. The conventional neighbour-targeting strategy only becomes optimal as available resources increase. Because this critical transition point shifts dynamically with the intervention budget, network topology, and spatial distribution of infections, static strategies inevitably fail. To overcome this, we develop Risk-Aware Isolation Learning (RAIL), a deep reinforcement learning framework that adaptively selects optimal interventions based on the evolving residual network. Across diverse synthetic and real-world networks, RAIL consistently maximizes population protection and suppresses outbreak spread. Ultimately, our findings challenge prevailing epidemiological intuitions, establishing a generalizable framework for adaptive interventions against localized risks in public health and other complex systems.

0.23

Multi-seed information diffusion with varying reproduction

cs.DS cs.DM ·2026-11-15 ·Erin Meger, Arianne Nantel, Nicholas Saloufakos, Jessica Enright
position similarity 0.57
Abstract · 11 page, 2 figures

We define the $S_hR_k$-process that generalizes the notion of Hamiltonicity through the lense of information diffusion. We say that a graph is $S_hR_k$-infectable if it can be fully infected by transmission trees seeded by at most $h$ initial infections in which each infection leads to at most $k$ others; or, equivalently, if it can be exactly vertex-covered by at most $h$ trees of degree at most $k$. While determining $S_hR_k$ infectability is NP-hard in general, we argue fixed-parameter tractability when parameterised by treewidth. Additionally, we give computational experimental results comparing the performance of several natural heuristics for minimising the number of initial infections required to an optimal LP-based approach on several standard complex network models. We find that a uniformly random approach outperforms greedy heuristics based on degree or clustering.

0.33