Social media advertisement has emerged as an effective approach for promoting the brands of a commercial house. Hence, many of them have started using this medium to maximize the influence among the users and create a customer base. In recent times, several companies have emerged as influence provider who provides views of advertisement content depending on the budget provided by the commercial house. In this process, the influence provider tries to exploit the information diffusion phenomenon of a social network, and a limited number of highly influential users are chosen and activated initially. Due to diffusion phenomenon, the hope is that the advertisement content will reach a large number of people. Now, consider that a group of advertisers is approaching an influence provider with their respective budget and influence demand. Now, for any advertiser, if the influence provider provides more or less influence, it will be a loss for the influence provider. It is an important problem from the influence provider’s perspective, as it must allocate seed nodes to advertisers to minimize loss. In this work, we study the problem of Regret Minimization in Social Media Advertisement (RMSMA). We propose a “regret model” that captures the aggregated loss encountered by the influence provider while allocating the seed nodes. We have shown that this problem is a computationally hard problem to solve. To address this, we propose three efficient heuristic algorithms: the Budget Effective Greedy approach, the Advertiser Elimination Approach, and the Advertiser-Driven Local Search (ADLS) approach. Extensive experiments on four real-world social network datasets—Congress-Twitter, Email-Eu-Core, Facebook, and Wikivote—under both Uniform and Trivalency influence probability settings demonstrate that our proposed algorithms significantly outperform baseline methods. In particular, ADLS consistently achieves the lowest total regret, reducing regret by up to <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$98\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>98</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> compared to random and Top-K baselines, and exhibits robust performance across all combinations of global and individual influence demand parameters.

A regret-aware framework for effective social media advertising

期刊论文
发表日期：

2026年5月9日

查看全文

Poonam Sharma,
Dildar Ali,
Suman Banerjee

摘要

Social media advertisement has emerged as an effective approach for promoting the brands of a commercial house. Hence, many of them have started using this medium to maximize the influence among the users and create a customer base. In recent times, several companies have emerged as influence provider who provides views of advertisement content depending on the budget provided by the commercial house. In this process, the influence provider tries to exploit the information diffusion phenomenon of a social network, and a limited number of highly influential users are chosen and activated initially. Due to diffusion phenomenon, the hope is that the advertisement content will reach a large number of people. Now, consider that a group of advertisers is approaching an influence provider with their respective budget and influence demand. Now, for any advertiser, if the influence provider provides more or less influence, it will be a loss for the influence provider. It is an important problem from the influence provider’s perspective, as it must allocate seed nodes to advertisers to minimize loss. In this work, we study the problem of Regret Minimization in Social Media Advertisement (RMSMA). We propose a “regret model” that captures the aggregated loss encountered by the influence provider while allocating the seed nodes. We have shown that this problem is a computationally hard problem to solve. To address this, we propose three efficient heuristic algorithms: the Budget Effective Greedy approach, the Advertiser Elimination Approach, and the Advertiser-Driven Local Search (ADLS) approach. Extensive experiments on four real-world social network datasets—Congress-Twitter, Email-Eu-Core, Facebook, and Wikivote—under both Uniform and Trivalency influence probability settings demonstrate that our proposed algorithms significantly outperform baseline methods. In particular, ADLS consistently achieves the lowest total regret, reducing regret by up to $98\%$ $98 %$ compared to random and Top-K baselines, and exhibits robust performance across all combinations of global and individual influence demand parameters.