Adaptive Multi-Feature Budgeted Profit Maximization in Social Networks

Tiantian Chen, Jianxiong Guo, Weili Wu

TL;DR

This paper introduces the "Multi-Feature Budgeted Profit Maximization" (MBPM) problem, which addresses how to maximize profit from product promotions in social networks when the product has multiple features that spread independently. They propose adaptive greedy algorithms that outperform non-adaptive methods by learning from diffusion results in real-time, achieving significant profit gains.

What Problem Does This Paper Address?

Online social networks are powerful tools for viral marketing. However, most existing research focuses on the spread of a single piece of information (e.g., a product announcement). In reality, a product has multiple features (like price, camera, battery life for a phone), and information about each feature can spread independently. A user's decision to purchase depends on their evaluation of all these features, not just one. This complexity makes traditional influence maximization (IM) problems insufficient. The authors tackle the challenge of maximizing profit from such multi-feature product promotions within a limited budget, considering that the decision of which users to target as initial spreaders can be made adaptively based on observed diffusion patterns.

Methods

The core of the paper lies in developing algorithms for the MBPM problem, particularly in an adaptive setting.

  • Multi-Feature Diffusion Model (MF-model): They extend existing models to account for multiple features, each with its own propagation probability. A user purchases the product only if the weighted sum of accepted features meets their personal threshold.
  • Non-Adaptive MBPM: They first formulate the problem for a scenario where all initial "seeds" (users to target) are chosen upfront. They prove the objective function is monotone submodular, allowing for a (1 - 1/e) approximation guarantee using a randomized greedy algorithm.
  • Adaptive MBPM: This is the main focus. Here, seeds are chosen one by one, and the decision for the next seed is informed by the diffusion results of previously chosen seeds.
  • Oracle Model: Assumes perfect knowledge of conditional expected marginal profit. They propose an adaptive greedy algorithm with a (1 - 1/e) approximation.
  • Noise Model: This is more realistic, where diffusion results are noisy. They adapt the EPIC algorithm to estimate conditional expected marginal profit and propose a "Sampled-AdapGreedy" algorithm. This algorithm uses a novel technique involving "Reverse Reachable (RR) sets" to estimate profits and achieves a (1 - e-(1-ε)) expected approximation guarantee.

Datasets

The authors evaluated their algorithms on six real-world social network datasets: Twitter, Wiki, Hamsterster, DBLP, HepPh, and Epinions. These datasets were used to test both the time efficiency and profit-maximization performance of their proposed adaptive policies against non-adaptive and heuristic adaptive baselines.

Key Insights and Ideas

  • Multi-feature diffusion is crucial: Ignoring product features leads to suboptimal profit maximization strategies.
  • Adaptivity pays off: Making decisions sequentially and learning from diffusion outcomes significantly boosts profit compared to pre-selecting all seeds.
  • Reverse Reachable sets are effective for noisy estimation: The paper introduces a clever way to estimate profits under uncertainty by leveraging reverse influence sampling, which is key to the performance of their adaptive algorithm in the noise model.
  • Heuristic adaptive policies are good, but adaptive greedy is better: While simple adaptive strategies like picking nodes with high degrees or profits offer improvements, their proposed adaptive greedy approach consistently yields higher profits.

Key Results

  • Profit Gains: Their proposed adaptive greedy policies (AG and SAG) consistently outperformed non-adaptive counterparts (MGMC, MGRIS) in terms of obtained profit across various datasets and budget levels. The SAG policy, in particular, achieved approximately 10% higher profits than the best heuristic adaptive policy (AMP).
  • Time Efficiency: The sampled adaptive greedy policy (SAG) was found to be the second fastest strategy, significantly faster than the Monte Carlo-based adaptive greedy (AG) and comparable to the reverse influence sampling-based non-adaptive algorithm (MGRIS). This suggests a good trade-off between performance and computational cost.
  • Approximation Guarantees: Theoretical analysis provides (1 - 1/e) and (1 - e-(1-ε)) expected approximation guarantees for their adaptive algorithms under oracle and noise models, respectively.

Limitations and Future Work

  • Oracle vs. Noise Model: While the oracle model provides a theoretical guarantee, the noise model's performance relies on the accuracy of the estimation techniques. The paper acknowledges that maximizing the estimation of profit might not perfectly align with maximizing the true profit, though their sampling techniques aim to mitigate this.
  • Computational Cost: Although SAG is efficient, the theoretical analysis for adaptive algorithms often involves polynomial time complexity, which can still be substantial for very large-scale networks.
  • Future Work: The paper implicitly suggests exploring more sophisticated estimation techniques for the noise model and potentially extending the MBPM problem to scenarios with more complex user behaviors or network dynamics. The effectiveness of their approach across diverse datasets hints at its generalizability.

Summary updated

Abstract

Online social network has been one of the most important platforms for viral marketing. Most of existing researches about diffusion of adoptions of new products on networks are about one diffusion. That is, only one piece of information about the product is spread on the network. However, in fact, one product may have multiple features and the information about different features may spread independently in social network. When a user would like to purchase the product, he would consider all of the features of the product comprehensively not just consider one. Based on this, we propose a novel problem, multi-feature budgeted profit maximization (MBPM) problem, which first considers budgeted profit maximization under multiple features propagation of one product. Given a social network with each node having an activation cost and a profit, MBPM problem seeks for a seed set with expected cost no more than the budget to make the total expected profit as large as possible. We consider MBPM problem under the adaptive setting, where seeds are chosen iteratively and next seed is selected according to current diffusion results. We study adaptive MBPM problem under two models, oracle model and noise model. The oracle model assumes conditional expected marginal profit of any node could be obtained in O(1) time and a (1-1/e) expected approximation policy is proposed. Under the noise model, we estimate conditional expected marginal profit of a node by modifying the EPIC algorithm and propose an efficient policy, which could return a (1-exp(ε-1)) expected approximation ratio. Several experiments are conducted on six realistic datasets to compare our proposed policies with their corresponding non-adaptive algorithms and some heuristic adaptive policies. Experimental results show efficiencies and superiorities of our policies.
BibTeX
@misc{chen2020adaptive,
  author = {Tiantian Chen and Jianxiong Guo and Weili Wu},
  title = {{Adaptive Multi-Feature Budgeted Profit Maximization in Social Networks}},
  year = {2020},
  eprint = {2006.03222},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.03222},
}

Loading related content...

Figure