Finding key players in complex networks through deep reinforcement learning.

Abstract

Finding an optimal set of nodes, called key players, whose activation (or removal) would maximally enhance (or degrade) certain network functionality, is a fundamental class of problems in network science^1,2. Potential applications include network immunization³, epidemic control⁴, drug design⁵, and viral marketing⁶. Due to their general NP-hard nature, those problems typically cannot be solved by exact algorithms with polynomial time complexity⁷. Many approximate and heuristic strategies have been proposed to deal with specific application scenarios^1,2,8-12. Yet, we still lack a unified framework to efficiently solve this class of problems. Here we introduce a deep reinforcement learning framework FINDER, which can be trained purely on small synthetic networks generated by toy models and then applied to a wide spectrum of influencer finding problems. Extensive experiments under various problem settings demonstrate that FINDER significantly outperforms existing methods in terms of solution quality. Moreover, it is several orders of magnitude faster than existing methods for large networks. The presented framework opens up a new direction of using deep learning techniques to understand the organizing principle of complex networks, which enables us to design more robust networks against both attacks and failures.