CS Paper Radar

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

Robbert van der Burg, Bernd Heidergott, Thao Le, Alessandro Zocca

cs.SI math.PRphysics.soc-ph ·submitted 2026-10-15 08:17 UTC · v1

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.

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

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

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

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

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

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

Shortest-path percolation and structural robustness of quantum internet networks

cs.SI physics.soc-phcond-mat.stat-mechquant-ph ·2026-11-16 ·Victor H. F. Francheto, Thomas Peron
code/data similarity 0.56
Abstract · 20 pages, 18 figures. Code available at https://github.com/VictorFrancheto/shortest-path-percolation-implementation

We study shortest-path percolation on spatial networks that model the quantum internet based on optical fibers. In this process, the removal of paths describes the consumption of the entangled links used for communication. We compare finite and unrestricted path-length bounds for networks whose average degree either increases with system size or remains approximately constant. We show that networks become more robust as the average degree increases, whereas networks with approximately constant average degree exhibit a data collapse for the fixed finite bounds considered. Using Monte Carlo sampling of the shortest-path-length distribution, we estimate an equivalent path cost, a finite bound that approximately reproduces the degradation of the network in the unrestricted case. For networks with fixed average degree, this cost grows approximately as the square root of the number of nodes. Increasing the bound beyond this value requires additional computation time without appreciably changing the percolation dynamics. As a complementary result, for Erdős-Rényi random networks, we find an empirical relation between the initial average degree and the approximately common crossing point of the percolation curves for different path-length bounds.

0.39