Deep Reinforcement Learning-Based Approach to Tackle Topic-Aware Influence Maximization

• Published in: Data science and engineering 2020-03, Vol.5 (1), p.1-11
• Main Authors: Tian, Shan, Mo, Songsong, Wang, Liwei, Peng, Zhiyong
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Artificial Intelligence; Chemistry and Earth Sciences; Computer Science; Data Mining and Knowledge Discovery; Database Management; Graph embedding; Influence maximization; Machine learning; Maximization; Optimization; Physics; Reinforcement learning; Social network; Social networks; Statistics for Engineering; Systems and Data Security
• ISSN: 2364-1185; 2364-1541
• DOI: 10.1007/s41019-020-00117-1

Motivated by the application of viral marketing , the topic-aware influence maximization (TIM) problem has been proposed to identify the most influential users under given topics. In particular, it aims to find k seeds (users) in social network G , such that the seeds can maximize the influence on users under the specific query topics and diffusion model such as independent cascade (IC) or linear threshold (LT). This problem has been proved to be NP-hard, and most of the proposed techniques suffer from the efficiency issue due to the lack of generalization. Even worse, the design of these algorithms requires significant specialized knowledge which is hard to be understood and implemented. To overcome these issues, this paper aims to learn a generalized heuristic framework to solve TIM problems by meta-learning. To this end, we first propose two topic-aware social influence propagation models based on IC and LT model, respectively, which is conducive to better advertising injections. We then encode the feature of each node by a vector and introduce a model, called deep influence evaluation model , to evaluate the user influence under different circumstances. Based on this model, we can construct the solution according to the influence evaluations efficiently, rather than spending a high cost to compute the exact influence by considering the complex graph structure. We conducted experiments on generated graph instances and real-world social networks. The results show the superiority in performance and comparable quality of our framework.