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

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.

Keywords

• Social network analysis
• influence maximization
• competitive influence maximization
• reinforcement learning