A Novel Nested Q-Learning Method to Tackle Time-Constrained Competitive Influence Maximization

Khurshed Ali, Chih-Yu Wang, Yi-Shin Chen

Abstract

Time plays a critical role in competitive influence maximization. Companies aim to promote their products before certain events, such as Christmas Eve or music concerts, to gain more benefit under competitions from other companies. Besides, these companies have a limited budget to spend on these product promotions. Therefore, in this paper, we examine a time-constrained competitive influence maximization where the parties wish to maximize their profits before the respective deadlines. Besides, the parties need to determine how to select the seed nodes and when to initiate information propagation in the network, such that the decision results in the optimal reward given the time and the budget constraint. To this end, we propose a novel reinforcement learning-based framework named seed-combination and seed-selection that is built on a nested Q-learning (NSQ) algorithm. This way, we can derive the optimal in both budget allocation and node selection that results in the maximum profit. In evaluating the proposed model, we consider the scenarios when the competitors’ strategy is known, unknown, and not available for training. The results show that the proposed NSQ algorithm could improve the rewards by up to 50% compared with the state-of-the-art algorithm, STORM-Q.

Introduction

Influence Maximization (IM) is the classic problem of finding a small set of "seed" users in a social network to trigger the largest possible word-of-mouth cascade. While well-studied, real-world scenarios add two messy variables: competition and time. Most existing models assume influence is static and campaigns last forever. In reality, companies compete for the same users, influence decays over time, and campaigns often have hard deadlines (e.g., a promotion ending on Christmas Eve).

This research addresses the Time-Constrained Competitive Influence Maximization (TC-CIM) problem. The challenge lies in optimally allocating a limited budget over several days while accounting for a competitor’s moves and the natural "fading" of social influence. This problem is computationally NP-hard, necessitating sophisticated algorithmic approaches.

Methodology

The authors propose the Seed-Combination and Seed-Selection (SCSS) framework, which relies on two major innovations:

1. TV-CLT Model

The Time-Varying Competitive Linear Threshold (TV-CLT) model incorporates time-decaying influence and propagation delays. In this model, the longer a party waits to activate a connection, the less "persuasive" it becomes, reflecting the reality of fading social trends.

Competitive influence propagation in a sample social network.

2. Nested Q-Learning (NSQ)

Standard Reinforcement Learning (RL) struggles with TC-CIM because the action space—every possible combination of nodes and timings—is too vast. NSQ solves this by nesting two Q-tables:

  • Outer Table (Seed-Combination): Learns the high-level strategy of when to invest the budget (e.g., all at once or spread out).
  • Inner Table (Seed-Selection): Given a timing strategy, it learns how to pick nodes using various heuristics like targeting high-degree nodes or "blocking" the competitor's neighbors.
The SCSS framework workflow.

For scenarios where the competitor's strategy is unknown, the authors use a self-play approach where two NSQ agents compete against each other to sharpen their strategies, similar to techniques used in training advanced AI like AlphaGo.

Experimental Evaluation

The researchers evaluated their method on six different network datasets to ensure robustness:

  • Collaboration Networks: Ca-HepTh and Ca-GrQc (Arxiv physics and relativity).
  • Communication Networks: P2P-Gnutella (file-sharing) and Facebook (social circles).
  • Biological & Synthetic: Celegan (neural network) and power-law synthetic networks.

Key Insights and Results

  • Timing as a Strategic Lever: The paper demonstrates that "front-loading" a budget (spending everything on Day 1) is not always the best move. If influence decays rapidly, saving budget to "re-ignite" or "block" specific areas later can yield higher total rewards.
  • Heuristics as Actions: Instead of picking individual nodes, the agent picks strategies (e.g., "Use the SubGreedy heuristic today"). This meta-learning approach makes training significantly more efficient.
  • Performance Boost: The NSQ algorithm outperformed STORM-Q (the previous state-of-the-art) by up to 50% in terms of total nodes influenced. It also consistently beat traditional greedy algorithms, which fail to account for temporal decay effectively.

Conclusion

The NSQ framework provides a robust solution for competitive influence maximization under time constraints. While currently dependent on the quality of underlying heuristics and requiring significant training time, it marks a major step forward in realistic social network modeling. Future work will focus on multi-party competition and more complex budget constraints.

Summary updated

Abstract

Time plays a critical role in competitive influence maximization. Companies aim to promote their products before certain events, such as Christmas Eve or music concerts, to gain more benefit under competitions from other companies. Besides, these companies have a limited budget to spend on these product promotions. Therefore, in this paper, we examine a time-constrained competitive influence maximization where the parties wish to maximize their profits before the respective deadlines. Besides, the parties need to determine how to select the seed nodes and when to initiate information propagation in the network, such that the decision results in the optimal reward given the time and the budget constraint. To this end, we propose a novel reinforcement learning-based framework named seed-combination and seed-selection that is built on a nested Q-learning (NSQ) algorithm. This way, we can derive the optimal in both budget allocation and node selection that results in the maximum profit. In evaluating the proposed model, we consider the scenarios when the competitors’ strategy is known, unknown, and not available for training. The results show that the proposed NSQ algorithm could improve the rewards by up to 50% compared with the state-of-the-art algorithm, STORM-Q.
BibTeX
@inproceedings{ali2018novel,
  author = {Khurshed Ali and Chih-Yu Wang and Yi-Shin Chen},
  title = {{A Novel Nested Q-Learning Method to Tackle Time-Constrained Competitive Influence Maximization}},
  booktitle = {IEEE Access},
  year = {2018},
  doi = {10.1109/access.2018.2888895},
}
Figure