Dismantling Efficiency and Network Fractality
arXiv:1804.10267 · doi:10.1103/PhysRevE.98.012316
Abstract
Network dismantling is to identify a minimal set of nodes whose removal breaks the network into small components of subextensive size. Because finding the optimal set of nodes is an NP-hard problem, several heuristic algorithms have been developed as alternative methods, for instance, the so-called belief propagation-based decimation (BPD) algorithm and the collective influence (CI) algorithm. Here, we test the performance of each of these algorithms and analyze them in the perspective of the fractality of the network. Networks are classified into two types: fractal and non-fractal networks. Real-world examples include the World Wide Web and Internet at the autonomous system level, respectively. They have different ratios of long-range shortcuts to short-range ones. We find that the BPD algorithm works more efficiently for fractal networks than for non-fractal networks, whereas the opposite is true of the CI algorithm. Furthermore, we construct diverse fractal and non-fractal model networks by controlling parameters such as the degree exponent, shortcut number, and system size, and investigate how the performance of the two algorithms depends on structural features.
arXiv comment7 pages, 6 figures
References in corpus (18)
- Community structure in social and biological networks
- The diameter of the world wide web
- Identification of influential spreaders in complex networks
- Attack vulnerability of complex networks
- Self-similarity of complex networks
- Influence maximization in complex networks through optimal percolation
- Universal Behavior of Load Distribution in Scale-free Networks
- Vital nodes identification in complex networks
- Percolation on sparse networks
- Network dismantling
- Skeleton and fractal scaling in complex networks
- Identifying optimal targets of network attack by belief propagation
- Statistical ensemble of scale-free random graphs
- Containing epidemic outbreaks by message-passing techniques
- Immunization and targeted destruction of networks using explosive percolation
- A box-covering algorithm for fractal scaling in scale-free networks
- Spin glass approach to the feedback vertex set problem
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes