Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach
This addresses the challenge of efficiently identifying influencers in social networks, offering a scalable solution with improved performance over existing methods, though it is incremental in its approach.
The paper tackles the NP-hard problem of influence maximization in complex networks by proposing DREIM, a deep reinforcement learning model that combines graph neural networks and reinforcement learning, achieving superior solution quality and linear scalability compared to state-of-the-art methods on large synthetic and real-world networks.
Maximizing influences in complex networks is a practically important but computationally challenging task for social network analysis, due to its NP- hard nature. Most current approximation or heuristic methods either require tremendous human design efforts or achieve unsatisfying balances between effectiveness and efficiency. Recent machine learning attempts only focus on speed but lack performance enhancement. In this paper, different from previous attempts, we propose an effective deep reinforcement learning model that achieves superior performances over traditional best influence maximization algorithms. Specifically, we design an end-to-end learning framework that combines graph neural network as the encoder and reinforcement learning as the decoder, named DREIM. Trough extensive training on small synthetic graphs, DREIM outperforms the state-of-the-art baseline methods on very large synthetic and real-world networks on solution quality, and we also empirically show its linear scalability with regard to the network size, which demonstrates its superiority in solving this problem.