Deep reinforcement learning breaks apart complex layered networks
Deep-learning-aided dismantling of interdependent networks
Social and Information Networks
Summary
Breaking a network into disconnected pieces by removing the fewest possible nodes is very hard, especially when the network has multiple interconnected layers. The authors introduce MultiDismantler, a method that uses deep reinforcement learning and treats the network as multiple layers working together. Trained on small examples, it performs much better on large real-world networks than older methods that only look at one layer at a time. This helps in tasks like controlling disease spread on social networks with many types of interactions and preventing failures in critical interconnected infrastructure systems.
What this means in practice
- •For public health planners: Design containment strategies in social networks with multiple types of social contacts to reduce disease spread effectively.
- •For critical infrastructure managers: Develop protocols to delay cascading failures in interconnected infrastructure systems by identifying critical nodes to manage.
Authors
Weiwei Gu, Chen Yang, Lei Li, Jinqiang Hou, Filippo Radicchi
Abstract
Identifying the minimal set of nodes whose removal breaks a complex network apart, also referred as the network dismantling problem, is a highly non-trivial task with applications in multiple domains. Whereas network dismantling has been extensively studied over the past decade, research has primarily focused on the formulations of the optimization problem for single-layer networks, neglecting that many, if not all, real networks display multiple layers of interdependent interactions. In such networks, the optimization problem is fundamentally different as the effect of removing nodes propagates within and across layers in a way that can not be predicted using a single-layer perspective. Here, we propose a dismantling algorithm named MultiDismantler, which leverages multiplex network representation and deep reinforcement learning to optimally dismantle multi-layer interdependent networks. MultiDismantler is trained on small synthetic multiplex graphs; when applied to large, real and synthetic networks, it displays exceptional dismantling performance, clearly outperforming all existing methods that rely on a single-layer approach to network dismantling. We show that MultiDismantler is effective in guiding strategies for the containment of diseases in social networks characterized by multiple layers of social interactions. Also, we show that MultiDismantler is useful in the design of protocols aimed at delaying the onset of cascading failures in interdependent critical infrastructures.