CS Paper Radar

Optimizing Marketing Budgets for Social Influence: A Generalized Fractional Incentives Framework

Abhishek K. Umrawal, Akhil Bhimaraju, Eliot W. Robson, Lav R. Varshney

cs.SI cs.AI ·submitted 2026-10-19 05:35 UTC · v1

Abstract

Marketing managers routinely allocate limited budgets across individuals in social networks whose responsiveness and influence vary substantially. We study the problem of Budgeted Generalized Fractional Influence Maximization (BGFIM), which captures the allocation of continuous levels of marketing spend across users in the presence of heterogeneous response and network spillovers. In this framework, adoption probabilities are governed by user-specific response functions that capture both baseline propensity and marginal responsiveness, while incentive costs vary across users. We propose a scalable solution approach based on a discrete greedy procedure with provable approximation guarantees, enabling tractable optimization under realistic budget constraints. Our formulation generalizes prior influence maximization models by allowing heterogeneous response and cost structures, providing a more flexible representation of targeted marketing interventions. Using experiments on multiple large-scale networks, we show that continuous allocation strategies can outperform standard heuristics and improve influence outcomes under heterogeneous conditions, and we illustrate how the framework can support profit-oriented decision making by identifying budget levels that balance marginal returns and costs. Overall, our results highlight the value of fine-grained budget allocation in networked marketing environments and offer a scalable approach for data-driven marketing resource allocation.

Comment
28 pages, 2 figures, and 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

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

Rewiring the Majority: Structural Median Opinion Control in the Friedkin-Johnsen Model

cs.SI ·2026-10-15 ·Elisabetta Biondi, Chiara Boldrini, Andrea Passarella, Marco Conti
similarity 0.60
Abstract · 11 pages,5 figures

Opinion control under the Friedkin-Johnsen (FJ) model has traditionally focused on modifying individual users, for example by changing their opinions or susceptibility to social influence. We study a complementary problem: can collective outcomes be steered by modifying the interaction network instead? We formulate structural median control as an edge-addition problem aimed at moving the equilibrium median beyond a target threshold. We show that the problem is NP-hard even under highly restricted settings and propose both continuous optimization methods and computationally lighter opinion-aware heuristics for selecting edge additions. Experiments on synthetic and real-world networks reveal that intervention success depends jointly on network topology, the placement of favorable opinions, and user susceptibility. Structural interventions produce the largest shifts when opinion placement and network structure allow added edges to create useful influence pathways toward the target outcome. Finally, under a homogeneous reference setting, we compare structural and node-level interventions using normalized budgets and a degree-weighted cost model. We show that, although node interventions often appear stronger under normalized budgets, structural interventions become competitive and frequently more cost-effective once the higher cost of targeting high-reach users is taken into account.

0.26

How Social Reinforcement Shapes Word-of-Mouth: A Conviction-Based Model for Marketing Diffusion and Network Targeting

cs.SI ·2026-10-09 ·Abhishek K. Umrawal, Curt Stutsman, Camille Woods, Eliot W. Robson
similarity 0.59
Abstract · 44 pages, 10 figures, and 2 tables

Organizations increasingly rely on social networks to drive product adoption and word-of-mouth diffusion, yet a central challenge is that consumers differ not only in whether they adopt but also in how strongly they subsequently advocate. In particular, individuals who adopt under strong social reinforcement often develop greater conviction and become more persuasive. Existing diffusion models largely abstract away from this mechanism by treating influence strength as static. We introduce a conviction-based diffusion framework, the Pressure Threshold (PT) model, that captures how social reinforcement shapes both adoption and subsequent advocacy. In this model, an individual's influence increases with the cumulative social pressure experienced at adoption, providing a tractable representation of conviction formation while preserving the interpretability of classical threshold-based models. We study the managerial implications of this mechanism through marketing targeting and seeding. We show that accounting for reinforcement fundamentally alters optimal targeting strategies, shifting emphasis toward consumers in cohesive network regions where repeated exposure can amplify downstream word-of-mouth. While reinforcement introduces nonstandard features into the optimization problem, we demonstrate that scalable heuristics remain effective and provide data-dependent performance guarantees. Across synthetic and real-world networks, we find that reinforcement often substantially increases the effectiveness of seeding interventions, particularly in dense and clustered environments where opportunities for social validation are abundant. Using time-stamped social media cascades, we further show that the PT model improves predictive accuracy relative to standard diffusion models, highlighting the empirical relevance of conviction-driven amplification.

0.47

Influence Ranking Improvement via Link Addition in Social Networks

cs.SI ·2026-09-29 ·Taiki Ikemoto, Sho Tsugawa
published similarity 0.59
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

From Prediction to Incrementality: Causal Optimization for Large-Scale Targeting and Recommendation

cs.LG cs.AI ·2026-08-10 ·Changshuai Wei, John Bencina, Phuc Nguyen, Andre Assuncao Silva T Ribeiro, Benjamin Zelditch
similarity 0.57
Abstract

Large-scale targeting and recommendation systems are typically built around predictive scores fed into heuristic or local allocation. When the business goal is incremental impact, as in marketing campaigns, incentives, and notifications, this paradigm systematically misallocates resources toward users who would have acted anyway. We present a decision-centric framework that instead optimizes causal effects under global constraints, aligning three components under a single objective: a causal neural network with a Transformer backbone for individual treatment-effect estimation, a Bayesian neural-bandit layer for uncertainty-aware exploration, and a dual-based large-scale linear-programming layer for constrained allocation. The framework also supports sequential context and multi-outcome, attribute-conditioned scoring through a Transformer encoder and outcome embeddings. We evaluate it with offline simulations on a public bandit dataset, targeted architectural ablations, and an online A/B test on LinkedIn Feed marketing traffic. We also distill production lessons on causal training-data construction and cost and delivery control, which were critical to successful deployment. The end-to-end treatment policy delivered a statistically significant $+7.20\%$ lift in the primary long-term-value metric, demonstrating the feasibility of production-scale causal optimization under business constraints.

0.04

On personal recommendations in social networks

eess.SY ·2026-09-15 ·Philipp Grünter, Karl Henrik Johansson, Angela Fontan
published similarity 0.57
Abstract · 7 pages, 2 figures, accepted to CDC 2026

Social networks in which algorithms actively influence humans through personal recommendations are ubiquitous. While opinion dynamics is an established tool to analyze these systems, existing models typically do not capture how individual agents process personal recommendations. In this work, we introduce a model for personal recommendations that is analytically tractable and consistent with the confirmation bias phenomenon from behavioral psychology. We describe how individuals process recommendations based on prior beliefs and a sensitivity parameter using a Gaussian influence function. Using this model, we analyze the effect of different recommendation policies. For broadcast policies, where recommendations are homogeneous across the agents, a bifurcation analysis shows that the system exhibits bistability, which may result in unintended consequences. For personally targeted policies, we first derive optimal personal recommendations and then extend to robust convergence when the agents' sensitivity to personal recommendations is uncertain. The collective behavior of the proposed model and the derived policies are illustrated and evaluated through numerical simulations.

0.24

Budget-Independent Influence Maximization in Nearly Linear Time

cs.DS cs.SI ·2026-09-20 ·Zhijie Zhang
similarity 0.56
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

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

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