Budgeted Online Influence Maximization

2026-04-22 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

This paper introduces a novel budgeted framework for online influence maximization (OIM), moving beyond traditional cardinality constraints to consider the total cost of an advertising campaign. The proposed approach better models real-world scenarios where influencer costs vary, allowing advertisers to optimize their overall social advertising budget. The authors present an algorithm, "boim-cucb," based on an independent cascade diffusion model and edge-level semi-bandit feedback. This algorithm utilizes a greedy technique to maximize the ratio of spread to cost, employing upper-confidence-bound (UCB) strategies for unknown diffusion parameters and costs. The framework also defines a new performance metric, approximation regret, for evaluating online policies in this budgeted setting. Theoretical analysis demonstrates logarithmic regret bounds, with further modifications (boim-cucb1, boim-cucb4, boim-cucb5) proposed to refine these bounds, particularly for scenarios with low seed set cardinality or improved confidence regions for weights. Experimental results illustrate the regret curves relative to the budget.

Key takeaway

For marketing strategists and data scientists designing viral marketing campaigns, this research suggests shifting from fixed influencer counts to a total budget constraint. Your strategy should focus on maximizing the "bang-per-buck" of influencers, selecting those who offer the greatest expected spread for their cost. Consider implementing an online learning approach to adapt to unknown network dynamics and influencer costs, continuously refining your seed set choices to optimize overall campaign effectiveness within your budget.

Key insights

A new budgeted online influence maximization framework optimizes total campaign cost, not just influencer count, using a ratio-maximizing greedy algorithm.

Principles

• Budget constraints better reflect real-world influencer marketing than cardinality limits.
• Online learning policies must balance exploration and exploitation to find optimal seed sets.
• Maximizing the ratio of influence spread to cost is key for budget-constrained campaigns.

Method

The boim-cucb algorithm uses UCBs to estimate unknown diffusion and cost parameters, then applies a greedy approach to maximize the bang-per-buck ratio (marginal spread/marginal cost) for seed set selection.

In practice

• Implement a global budget for influencer campaigns, not per-round limits.
• Prioritize influencers based on their cost-effectiveness (spread per dollar).
• Use Monte Carlo simulations to estimate spread for efficient greedy algorithm execution.

Topics

• Budgeted Influence Maximization
• Social Advertising
• Multi-armed Bandits
• Independent Cascade Model
• Submodular Optimization

Best for: AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• Constrained user-item allocation for e-commerce marketing campaigns — Constrained spectral biclustering effectively auto-targets e-commerce campaigns by jointly optimizing user-item allocation for quality and fairness.
• Online LLM Selection via Constrained Bandits with Time-Varying Demand — Online LLM selection under dynamic demand and hard/soft constraints can be optimized using constrained bandit learning.
• Predicting Online News Popularity: A Machine Learning Project That Taught Me More About Data… — Log-transforming skewed target variables is critical for effective predictive modeling of online content popularity.
• DIY AI & ML: Solving The Multi-Armed Bandit Problem with Thompson Sampling — Thompson Sampling automates decision-making by balancing exploration and exploitation to optimize outcomes faster than A/B testing.
• Three-in-One World Model: Energy-Based Consistency, Prediction, and Counterfactual Inference for Marketing Intervention — A DBM-based world model with task-specific adapters unifies prediction, consistency, and counterfactual inference for marketing interventions.
• Cracking the Cold Start Problem — Hybrid recommender systems combining collaborative filtering, embeddings, and bandit learning improve cold start and fairness.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.