Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
arXiv:2208.07792 · doi:10.1145/3511808.3557290
Abstract
Can we employ one neural model to efficiently dismantle many complex yet unique networks? This article provides an affirmative answer. Diverse real-world systems can be abstracted as complex networks each consisting of many functional nodes and edges. Percolation theory has indicated that removing only a few vital nodes can cause the collapse of whole network. However, finding the least number of such vital nodes is a rather challenging task for large networks due to its NP-hardness. Previous studies have proposed many centrality measures and heuristic algorithms to tackle this network dismantling (ND) problem. Different from theirs, this article tries to approach the ND task by designing a neural model which can be trained from tiny synthetic networks but will be applied for various real-world networks. It seems a discouraging mission at first sight, as network sizes and topologies are quite different across distinct real-world networks. Nonetheless, this article initiates insightful efforts of designing and training a neural influence ranking model (NIRM). Experiments on fifteen real-world networks validate its effectiveness for its mostly requiring fewer vital nodes to dismantle a network, compared with the state-of-the-art competitors. The key to its success lies in that our NIRM can efficiently encode both local structural and global topological signals for ranking nodes, in addition to our innovative labelling method in training dataset construction.
arXiv commentTo be published at CIKM 2022 as a full paper
References in corpus (26)
- A Comprehensive Survey on Graph Neural Networks
- Catastrophic cascade of failures in interdependent networks
- Network robustness and fragility: Percolation on random graphs
- Structural Vulnerability of the North American Power Grid
- Influence maximization in complex networks through optimal percolation
- Prediction and predictability of global epidemics: the role of the airline transportation network
- Growing Scale-Free Networks with Tunable Clustering
- Learning Combinatorial Optimization Algorithms over Graphs
- Graph Contrastive Learning with Augmentations
- Modeling the Internet's Large-Scale Topology
- Recent advances in percolation theory and its applications
- Percolation on sparse networks
- Network dismantling
- Generalized Network Dismantling
- Combinatorial Optimization with Physics-Inspired Graph Neural Networks
- Identifying optimal targets of network attack by belief propagation
- Fast and simple decycling and dismantling of networks
- Machine learning dismantling and early-warning signals of disintegration in complex systems
- Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks
- The dynamical structure of political corruption networks
- Machine Learning in Network Centrality Measures: Tutorial and Outlook
- Approximating Network Centrality Measures Using Node Embedding and Machine Learning
- Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
- Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach
- Parametric UMAP embeddings for representation and semi-supervised learning
- Revealing the structure of the world airline network