CS Paper Radar

Efficient Influence Minimization via Source-Integrated Sampling

Jingbang Chen, Junyao Wang

cs.SI cs.DS ·submitted 2026-11-11 19:41 UTC · v1
theory

Abstract

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.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-09-17 ·Matic Požar
similarity 0.69
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

Budget-Independent Influence Maximization in Nearly Linear Time

cs.DS cs.SI ·2026-09-20 ·Zhijie Zhang
similarity 0.68
Abstract

Influence maximization asks for $k$ seed vertices that maximize the expected spread of a diffusion process in a network. Standard near-optimal-time algorithms based on reverse-reachable sampling achieve a $(1-1/e-\varepsilon)$ approximation, but their expected running-time bounds grow linearly with the seed budget $k$. We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least $1-δ$ in $O((m+n)\varepsilon^{-3}\log(2n/δ))$ expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve $O(\varepsilon k)$ seed positions for cost-weighted random vertices, allowing reverse-reachable searches to stop as soon as they encounter a reserved seed. An independent sample-count estimation phase uses a statistic that also controls the expected search cost. Matching these quantities eliminates the multiplicative dependence on $k$ while preserving the approximation guarantee.

0.38

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

Influence Ranking Improvement via Link Addition in Social Networks

cs.SI ·2026-09-29 ·Taiki Ikemoto, Sho Tsugawa
published similarity 0.61
Abstract · 15 pages; accepted at ASONAM 2026

Social media platforms increasingly rely on influential users for information dissemination in domains such as marketing and political campaigns. As the value of being recognized as influential grows, users may have incentives to strategically enhance their influence. In this study, we investigate whether and to what extent the influence ranking of a target node can be improved by adding a limited number of outgoing links in the context of influence maximization (IM). We formulate the Link Selection Problem for Influence Ranking Improvement (LSP-IRI) as the problem of selecting a fixed-size set of additional outgoing links from a target node in order to maximize its rank improvement. To examine this problem, we consider two representative heuristic strategies: a greedy method that directly optimizes rank improvement and a computationally efficient random search method. We conduct experiments on four real-world networks ranging from thousands to hundreds of thousands of nodes. The results show that even a few added links can substantially improve IM-based influence rankings. In particular, the greedy method improves the ranks of nodes initially ranked around 50 by several tens of positions on average with only three added links, sometimes moving them into the top 10. The random search method achieves smaller gains under strict budgets but reduces computation time by up to approximately 98% compared with the greedy method and becomes effective when larger budgets are allowed. These findings show that IM-based influence rankings are sensitive to limited local structural modifications and highlight a trade-off between ranking improvement and computational efficiency.

0.33

Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach

cs.LG cs.SI ·2026-09-12 ·Erfan Ahmadi, Mina Shirazi, Behnam Bahrak
similarity 0.61
Abstract · 16 pages, 1 figure, 4 tables. Submitted to the International Journal of Data Science and Analytics

The Minimum Dominating Set (MDS) problem is a classic NP-hard combinatorial optimization problem with critical applications in social network analysis, including viral marketing, influence maximization, public health interventions, and information dissemination. Identifying a minimal set of influential individuals whose reach covers an entire social network is central to these applications, yet remains computationally challenging at scale. Graph neural networks (GNNs) have emerged as powerful tools for learning over graphs, and recent work explores their application to hard combinatorial problems. This paper presents a novel unsupervised GNN framework for the MDS problem that eliminates the need for ground-truth solutions during training. Trained on 12,000 synthetic graphs with diverse structural properties, our method achieves up to 55x faster inference than metaheuristic baselines and up to 14x faster inference than supervised learning approaches, while finding optimal or near-optimal dominating sets on real-world social network benchmarks. Our learned heuristic generalizes effectively to unseen graph distributions, demonstrating strong practical applicability for large-scale social network analysis.

0.23

Algorithmic Fairness for Influence Maximization: A Survey of Models, Metrics, and Optimization Techniques

cs.SI ·2026-10-14 ·Shashank Sheshar Singh, Sunil Kumar Meena, Kuldeep Singh, krati Saxena
survey similarity 0.60
Abstract

Influence maximization (IM) has become a basis of modeling information spread across social networks, with applications in viral marketing, public health, and political campaigns. However, classical IM algorithms often prioritize the spread of overall influence and ignore its fairness, resulting in disadvantages for marginalized or underrepresented communities. This survey provides a detailed look at fairness-aware influence maximization, focusing on important challenges, models, and methods designed to ensure fair influence maximization. We categorize existing methods into five groups based on their fairness objectives, including parity, diversity, and utility, and discuss how they handle biased network structure, protected attributes, and seeding constraints. We also examine how fairness-aware influence maximization methods perform on real-world data to highlight the importance of combining fairness with classical influence maximization methods. By bridging the gap between influence spread and social equity, this survey lays the foundation for designing fair algorithms that ensure fair representation in large-scale diffusion processes. The survey concludes by outlining emerging trends, open challenges, and prospective future directions in the domain, highlighting the need for expertise spanning multiple disciplines.

0.07

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

Optimal Sample Complexity for Max-Cut

cs.DS ·2026-11-02 ·Itamar Bender, Robert Krauthgamer
theory similarity 0.59
Abstract

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.

0.21