Finding key players in complex networks through deep reinforcement learning

By Changjun Fan, Li Zeng, Yizhou Sun, Yang-Yu Liu. Nature Machine Intelligence, 2020

386 citations recorded by the source corpus.

Finding an optimal set of nodes, called key players, whose activation (or removal) would maximally enhance (or degrade) a certain network functionality, is a fundamental class of problems in network science. Potential applications include network immunization, epidemic control, drug design and viral marketing. Due to their general NP-hard nature, these 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. 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 application scenarios. 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. A fundamental problem in network science is how to find an optimal set of key players whose activation or removal significantly impacts network functionality. The authors propose a deep reinforcement learning framework that can be trained on small networks to understand the organizing principles of complex networked systems.

Subfields: Experimental and Cognitive Psychology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a7aaf9d1c177366f522010d305cad3d4441e2ab6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Experimental and Cognitive Psychology

In Statistical and Nonlinear Physics

Citations in the corpus

Robustness and resilience of complex networks (2024, background): “However, whereas GDM learns in a supervised manner on networks dismantled optimally via brute force, FINDER learns in a reinforcement fashion.”