CS Paper Radar

Fast and Scalable Influence Estimation in the Independent Cascade Model: a unified framework

Matic Požar, Miklós Krész

cs.SI ·submitted 2026-10-23 11:24 UTC · v1
benchmark

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.

Closest papers

Nearest neighbours by meaning across the whole index.

From Content Sharing to Opinion Shaping: A Theoretical Framework for Cascade-Driven Opinion Dynamics

cs.SI ·2026-10-14 ·Elisabetta Biondi, Chiara Boldrini, Andrea Passarella, Marco Conti
similarity 0.67
Abstract · 13 pages, 7 figures

Online social networks (OSNs) tightly couple information diffusion and opinion formation, yet most existing models treat these processes separately. Building on the Friedkin-Johnsen on Cascades (FJC) model, which integrates opinion updating within stochastic information cascades, we advance its analytical characterization and systematic validation. We derive an exact conditional layer-wise recursion that reveals the statistical coupling between diffusion realizations and opinion evolution, showing that a closed-form recursion in unconditional expectations is not available. To overcome this limitation, we introduce a mean-field decoupling approximation (MFA) that yields a tractable linear recursion for the expected opinion trajectory. We also develop scalable tree-based reductions that drastically reduce computational complexity while preserving structural diffusion properties, and validate the analytical recursion and its approximations through extensive simulations. Using Stochastic Block Model networks with controlled initial opinion configurations, we show that, unlike the classical Friedkin-Johnsen model, which typically leads to global homogenization, the FJC dynamics generate richer regimes of bounded assimilation and sustained polarization. Overall, this work bridges diffusion and influence modeling, providing a theoretical foundation for understanding how cascade-driven interactions reshape collective opinion landscapes in structured social networks.

0.27

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

Exact Greedy Influence Maximization in Linear Time on Bounded-Treewidth Graphs

cs.DS ·2026-09-17 ·Matic Požar
similarity 0.65
Abstract · 22 pages, 2 figures, 2 tables

Computing influence spread under the Independent Cascade (IC) model is #P-hard, and influence maximization is commonly approached using Monte Carlo or reverse-reachable-set sampling. We study IC diffusion on bounded-treewidth graphs. Using probability distributions over separator reachability relations, we obtain exact influence evaluation in $O(n2^{O(w^2)}\operatorname{poly}(w))$ time for a graph with $n$ nodes and treewidth $w$. Our main contribution is an exact all-marginal-gains algorithm. We introduce variable artificial source edges and show that, at a deterministic seed set, the derivative with respect to each source-edge probability equals the corresponding greedy marginal gain. Reverse-mode differentiation therefore computes all marginal gains simultaneously with the same asymptotic complexity as one exact influence evaluation. This yields an exact implementation of classical greedy influence maximization in $O(Kn2^{O(w^2)}\operatorname{poly}(w))$ time, linear in graph size for fixed $w$ and seed budget $K$. We also show that the separator-relation representation has tight $2^{Θ(w^2)}$ state complexity within exact context-independent compositional separator summaries. This contrasts with the NP-hardness of globally optimal IC influence maximization already on graphs of treewidth one and pathwidth two. Experiments on synthetic bounded-treewidth networks are consistent with linear scaling for fixed width and show that runtime is largely insensitive to propagation and seed-activation probabilities. In demanding diffusion regimes, the method substantially outperforms reverse-reachable-set and optimized Monte Carlo greedy baselines while computing greedy marginal gains exactly.

0.30

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

Optimal and heuristic strategies for evaluating the influence of coordinated behavior in information cascades and retweet networks

cs.SI cs.CY ·2026-09-21 ·Niccolò Di Marco, Matteo Cinelli, Shinichi Nakano, Andrea Frosini
theory similarity 0.65
Abstract

Coordinated Inauthentic Behavior (CIB) has become a major concern in online social platforms, yet its actual impact on information diffusion remains poorly understood. Existing research has primarily focused on detecting coordinated activity, while comparatively little attention has been devoted to quantifying its influence once detected. In this work, we introduce two complementary frameworks for the post-hoc evaluation of coordinated accounts. First, we formulate the problem on information cascades as a constrained influence maximization problem over directed trees and develop a polynomial-time dynamic programming algorithm that computes the optimal placement of coordinated nodes, providing an upper bound on their achievable influence. Second, motivated by the limited availability of diffusion cascades in real-world platforms, we propose a network-based framework that estimates influence directly from retweet networks using the independent cascade model and compares the observed placement of coordinated accounts against established heuristic baselines. We evaluate both approaches on Twitter/X data from the 2019 UK General Election and on a collection of verified state-backed information operation campaigns spanning multiple countries. While coordinated accounts exhibit limited influence in the UK cascades, the network-based analysis reveals substantial differences across campaigns, with several operations achieving influence comparable to or exceeding that of structurally central seed sets. Finally, by reconstructing cascades from the retweet networks, we show that the two frameworks produce consistent results, suggesting that the observed effects reflect intrinsic structural properties of coordinated activity rather than artifacts of the underlying methodology.

0.28

CSBA-Net: Learning Cross-Scale Structural Dependencies for Influential Node Identification in Complex Networks

cs.SI ·2026-10-13 ·Rihab Boukheche, Mohammed Lalou, Nardjes Bouchemal
similarity 0.63
Abstract

Identifying influential nodes is a fundamental task in complex network analysis, with applications in epidemic control, information diffusion, and network robustness. Existing centrality-based and learning-based methods often provide limited integration of structural information across different network scales. To address this limitation, we propose CSBA-Net, for Cross-Scale Structural BiGRU Attention Network, a multi-scale structural representation learning framework that jointly captures local, community-level, and global structural patterns. The extracted representations are processed by CNNs and integrated through a BiGRU with multi-head self-attention to model dependencies across structural scales. Influential-node scores are learned through regression using SIR-based diffusion simulations as reference targets. We conduct experiments on 24 real-world and 12 synthetic networks from social, biological, technological, and knowledge domains, and show that CSBA-Net achieves Kendall's tau=0.802, Spearman's rho=0.943, NDCG10 =0.898, and NDCG20 =0.916, outperforming the considered centrality-, CNN-, and GNN-based baselines. The results demonstrate the effectiveness of combining complementary structural scales for accurate influential-node ranking across diverse network structures.

0.12

Efficient Influence Minimization via Source-Integrated Sampling

cs.SI cs.DS ·2026-11-11 ·Jingbang Chen, Junyao Wang
theory similarity 0.63
Abstract · 14 pages

Influence minimization by node blocking is a fundamental problem in graph data management that seeks a small set of vertices whose removal minimizes the expected spread from a fixed source set. It supports decisions about where to intervene in large interaction networks to control harmful propagation, such as the spread of rumors and infectious diseases. Under the Independent Cascade (IC) model, selecting blockers requires comparing a large number of candidate sets, and estimating their effects on propagation can be costly. We propose SIG (Source-Integrated Greedy), a sampling framework for efficiently finding high-quality approximate solutions. Our key idea is to group the possible sets of neighbors directly activated by the sources according to their effects on blocker selection. SIG represents these groups in a compact weighted tree and computes their probabilities directly, allowing each sample to account for all source outcomes without enumerating them. We prove that SIG produces unbiased estimates of the lower-bound objective without increasing variance for fixed blocking plans, and establish a high-probability quality guarantee through independent validation. Extensive experiments on real-world networks show that SIG has the lowest mean total running time in all main comparisons, with speedups of up to 583x over the fastest baseline. SIG produces solutions competitive with those of prior methods and achieves the highest influence reduction in multiple settings, including on many of the largest networks, where several baselines exceed the runtime limit. Additional experiments show that SIG maintains consistently low running times as graph size and the blocking budget increase, while delivering stronger blocking solutions at larger budgets.

0.18

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