CS Paper Radar

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

Nguyen Hong Phuc, Duong Khanh Ly, Hoang Phi Dung

cs.SI cs.NImath.OC ·submitted 2026-09-27 15:43 UTC · v1
theory

Abstract

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.

Comment
Welcome comments

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

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

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.63
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.62
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

A Networked SIS Epidemic--Opinion Model with Higher-Order Interactions

eess.SY ·2026-08-31 ·Saba Samadi, José I. Caiza, Sebin Gracy, Philip E. Paré
published similarity 0.62
Abstract · Accepted to the 65th IEEE Conference on Decision and Control (CDC)

This paper studies a susceptible--infected--susceptible (SIS) epidemic model coupled with opinion dynamics over a network of communities with higher-order interactions. Unlike standard networked SIS models, which account only for pairwise transmission, the proposed model incorporates group-level infection mechanisms and feedback between epidemic prevalence and community opinions. We establish local stability and instability conditions for a particular healthy equilibrium, derive a sufficient condition for global exponential eradication of the infection state, and identify conditions under which higher-order interactions induce bistability in the reduced dynamics on a positively invariant synchronous set. These results characterize how higher-order interactions alter the dynamics of opinion-dependent epidemic systems. Numerical simulations illustrate the predicted eradication, bistable, and endemic regimes.

0.27

Comparing Probabilistic Influence-Spreading Centralities to Commonly-Used Centrality Measures in Directed and Weighted Networks

cs.SI ·2026-08-19 ·Juuso Luhtala, Vesa Kuikka, Kimmo K. Kaski
similarity 0.62
Abstract

The Influence-Spreading Model (ISM) introduces three probabilistic centrality measures: out-centrality, in-centrality, and ISM betweenness centrality. Out-centrality measures the average probability that a node influences others, while in-centrality measures the average probability that others influence a node. ISM betweenness centrality measures the change in total probabilistic influence when a node is removed. These measures depend on edge transmission probabilities and allow walks up to a specified maximum length. We compare the ISM centrality measures to commonly used weighted variants of out-degree, in-degree, closeness, shortest-path betweenness, and Katz centrality in directed, weighted networks using four real-world online social networks and nine synthetic networks generated by Erdős-Rényi, navigable small-world, and directed scale-free models. For the synthetic networks, the edge probabilities are drawn from three beta distributions. We evaluate the similarity in centrality values and their ranking using Pearson correlation and Spearman's rank correlation coefficients. Results show strong correlations between the ISM out-centrality and weighted out-degree and outward Katz centrality, particularly for low edge probabilities. Conversely, relationships between the ISM in-centrality and other measures vary with network topology, sometimes yielding negative correlations. Correlations between the ISM betweenness and the shortest-path betweenness are also topology-dependent and weaken as alternative influence paths become more relevant. Overall, standard centrality measures can approximate the influence of broadcasting influence but often miss the nuances of receiving influence and probabilistic intermediary roles.

0.18

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