Fast and scalable methods improve influence estimation on social networks
Fast and Scalable Influence Estimation in the Independent Cascade Model: a unified framework
Social and Information Networks
Summary
Predicting how information or behavior spreads in a network is important but very hard to do exactly. The paper studies and compares different fast ways to estimate how likely each person will be influenced in a popular spreading model called the independent cascade model. The authors connect many existing methods within a single framework and propose a new approach that balances accuracy and speed. Their tests on many real and synthetic networks show that this new method is often the best at estimating influence probabilities efficiently.
What this means in practice
- •For social media platform engineers: Improve the speed and accuracy of estimating how posts spread in social networks for better content recommendation and moderation tools.
- •For epidemic modeling teams: Speed up simulations of disease spread by using accurate approximate methods to estimate infection probabilities across contact networks.
Authors
Matic Požar, Miklós Krész
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.