CS Paper Radar

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

Michele Tizzani

cs.SI physics.soc-ph ·submitted 2026-09-09 16:20 UTC · v2
published

Abstract

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.

Comment
24 pages, 8 figures; 43 pages Supplementary Material

Closest papers

Nearest neighbours by meaning across the whole index.

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

Finding Patient Zero in Temporal Contact Networks: A Comparative Study

cs.SI ·2026-11-17 ·Nathan Cincera Brack, Martin Sterchi, Lorenz Hilfiker, Abraham Bernstein
similarity 0.59
Abstract · 21 pages (18 main text, 3 supplementary), 11 figures, 5 tables. This work has been submitted to the IEEE for possible publication

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.

0.35

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

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

Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations

cs.IT ·2026-09-09 ·Plínio Santini Dester
similarity 0.58
Abstract · Submitted to Wireless Networks

Decentralized networks can learn collision-free periodic transmission schedules, but acquisition can consume much of a finite operating horizon. We characterize acquisition in a reservation protocol for a fixed population of $n$ nodes and a period of $Γ_n\ge n$ slots. Initially, each node attempts independently in each slot with probability proportional to $1/n$. A success reserves a slot that the node reuses every $Γ_n$ slots, retaining it after collisions. Nodes use only their own acknowledgments and small local memory. An exact finite-population Markov reduction, independent of the arrangement of reserved slots, characterizes the time until every node has a distinct reservation. As $n\to\infty$, mean acquisition takes $O(n^2)$ slots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, for fixed $θ>0$. With a fixed number $Γ_n-n$ of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while $Γ_n/n$ remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $o(n^2)$ mean acquisition while long-run utilization, the fraction $n/Γ_n$ of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.

0.31

Influence of Assortativity on the SICP Spreading Process in Hypergraphs

cs.SI physics.soc-ph ·2026-11-11 ·Jelmer Stolwijk, Renze Dijkhuizen, H. A., Peters, Huijuan Wang
similarity 0.58
Abstract

Many real-world systems involve group interactions that cannot be captured by pairwise graphs. They can be better represented by hypergraphs where each hyperedge could connect an arbitrary number of nodes. The Susceptible-Infected Contact Process (SICP) has been proposed to model the spreading of information and epidemics on hypergraphs. However, how higher-order topological properties of a hypergraph influence the SICP spreading process remains understudied. In this paper, we examine the impact of hypergraph assortativity based on the Neighborhood Coefficient (NC)-the average size of hyperedges incident to a node-on the SICP spreading process. By introducing a low-complexity measure of hypergraph assortativity grounded in analysis of variance, we apply hyperdegree-preserving rewirings to real-world networks and synthetic hypergraph models to tune their assortativity. We find and explain why lower NC assortativity yields higher average epidemic prevalence and lower prevalence variance across different seed selections. This phenomenon is evident when hyperdegree-preserving rewirings are applied to real-world networks with heterogeneous topological structures, but it is largely absent when comparing synthetic random hypergraphs to their rewired counterparts.

0.15

MambaTG: Candidate-Aware State Space Modeling for Future Link Prediction on Temporal Graphs

cs.LG ·2026-11-05 ·Nguyen Hong Quan, Sitao Luan, Yilun Zheng, Lihui Chen
similarity 0.57
Abstract

Future link prediction on temporal graphs involves both repeated interactions between previously connected node pairs and first-time interactions between pairs with no prior interaction. While repeated-edge prediction can exploit direct pairwise evidence, unseen-edge prediction must generalize beyond historical recurrence. Existing temporal graph models often exploit signals tied to recurring interactions or historical overlap, which are highly informative for repeated edges but become limited or unavailable for unseen edges, contributing to substantial performance degradation on unseen-edge prediction. Based on this observation, we identify two complementary signals for modeling sequential dynamics beyond historical recurrence: (1) historical-sequence evolution, which captures dependencies among the source node's chronologically ordered interactions, and (2) candidate--history compatibility, which captures how well a candidate fits the source node's evolving history. Based on the decomposition, we propose MambaTG, a candidate-aware Mamba-based framework that jointly models these two signals. Mamba provides a natural mechanism for this design: its selective recurrence captures the evolution of ordered interaction histories, while its input-dependent state transitions allow the history state to adapt to different candidate inputs. Extensive experiments on 13 temporal graph datasets against 13 representative baselines show that MambaTG achieves strong and consistent performance across both repeated and unseen edges while remaining computationally efficient.

0.20

Network topology shapes consensus and vulnerability in LLM populations

cs.AI physics.soc-phcs.CY ·2026-10-22 ·Roberto Passaro, Ariel Flint, Romualdo Pastor-Satorras, Andrea Baronchelli, Luca Maria Aiello
similarity 0.57
Abstract

As large language models (LLMs) are deployed in interacting populations, their collective behaviour depends not only on the models but also on who interacts with whom. Studies of convention formation in LLM populations have mainly tested well-mixed interactions. We place policies extracted from four LLMs on fully connected, random regular, and heterogeneous networks, with $10^3$ to $10^5$ agents playing the naming game. Topology affects how quickly consensus emerges, sometimes whether it emerges at all, and, in rare cases, which convention wins. Sparsest networks slow consensus up to twelvefold. Yet, by preserving correlations between persistent neighbours, they restore consensus in some cases that fail to converge under well-mixed interactions. Networks also govern vulnerability to adversarial attack. We measure the critical mass of committed agents needed to overturn an established convention. Tipping thresholds follow the same ordering across models and conditions: hubs $\leq$ random $\leq$ low-degree nodes. On the most heterogeneous topology, median critical masses are 3%, 16%, and 35%, respectively; targeting hubs requires one-sixth as many committed agents as random placement. For most models, networked populations are easier to tip than well-mixed ones, so well-mixed estimates can overstate robustness. Assessing the safety of multi-agent AI requires mapping who interacts with whom.

0.44