Diverse real world systems can be abstracted as complex networks consisting of nodes and edges as functional components. Percolation theory has shown that the failure of a few of nodes could lead to the collapse of a whole network, which brings up the network dismantling problem: How to select the least number of nodes to decompose a network into disconnected components each smaller than a predefined threshold? For its NP-hardness, many heuristic approaches have been proposed to measure and rank each node according to its importance to network structural stability. However, these measures are from a uniscale viewpoint by regarding one complex network as a flatted topology. In this article, we argue that nodes' structural importance can be measured in different scales of network topologies. Built upon recent deep learning techniques, we propose a self-supervised learning based network dismantling framework (NEES), which can hierarchically merge some compact substructures to convert a network into a coarser one with fewer nodes and edges. During the merging process, we design neural models to extract essential structures and utilize self-attention mechanisms to learn nodes' importance hierarchy in each scale. Experiments on real world networks and synthetic model networks show that the proposed NEES outperforms the state-of-the-art schemes in most cases in terms of removing the least number of target nodes to dismantle a network. The dismantling effectiveness of our neural extraction framework also highlights the emerging role of multi-scale essential structures.
Paper
Full text
Neural extraction of multiscale essential structure for network dismantling
Semantic Scholar · Computer Science · 2022
Abstract
Diverse real world systems can be abstracted as complex networks consisting of nodes and edges as functional components. Percolation theory has shown that the failure of a few of nodes could lead to the collapse of a whole network, which brings up the network dismantling problem: How to select the least number of nodes to decompose a network into disconnected components each smaller than a predefined threshold? For its NP-hardness, many heuristic approaches have been proposed to measure and rank each node according to its importance to network structural stability. However, these measures are from a uniscale viewpoint by regarding one complex network as a flatted topology. In this article, we argue that nodes' structural importance can be measured in different scales of network topologies. Built upon recent deep learning techniques, we propose a self-supervised learning based network dismantling framework (NEES), which can hierarchically merge some compact substructures to convert a network into a coarser one with fewer nodes and edges. During the merging process, we design neural models to extract essential structures and utilize self-attention mechanisms to learn nodes' importance hierarchy in each scale. Experiments on real world networks and synthetic model networks show that the proposed NEES outperforms the state-of-the-art schemes in most cases in terms of removing the least number of target nodes to dismantle a network. The dismantling effectiveness of our neural extraction framework also highlights the emerging role of multi-scale essential structures.