Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
arXiv:2003.04713 · doi:10.1016/j.eswa.2019.112853
Abstract
Many real-world applications can be modelled as complex networks, and such networks include the Internet, epidemic disease networks, transport networks, power grids, protein-folding structures and others. Network integrity and robustness are important to ensure that crucial networks are protected and undesired harmful networks can be dismantled. Network structure and integrity can be controlled by a set of key nodes, and to find the optimal combination of nodes in a network to ensure network structure and integrity can be an NP-complete problem. Despite extensive studies, existing methods have many limitations and there are still many unresolved problems. This paper presents a probabilistic approach based on neighborhood information and node importance, namely, neighborhood information-based probabilistic algorithm (NIPA). We also define a new centrality-based importance measure (IM), which combines the contribution ratios of the neighbor nodes of each target node and two-hop node information. Our proposed NIPA has been tested for different network benchmarks and compared with three other methods: optimal attack strategy (OAS), high betweenness first (HBF) and high degree first (HDF). Experiments suggest that the proposed NIPA is most effective among all four methods. In general, NIPA can identify the most crucial node combination with higher effectiveness, and the set of optimal key nodes found by our proposed NIPA is much smaller than that by heuristic centrality prediction. In addition, many previously neglected weakly connected nodes are identified, which become a crucial part of the newly identified optimal nodes. Thus, revised strategies for protection are recommended to ensure the safeguard of network integrity. Further key issues and future research topics are also discussed.
arXiv comment25 pages, 13 figures, 2 tables
References in corpus (24)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- Cooperative Game Theory Approaches for Network Partitioning
- Catastrophic cascade of failures in interdependent networks
- Identification of influential spreaders in complex networks
- Resilience of the Internet to random breakdowns
- Attack vulnerability of complex networks
- Breakdown of the Internet under intentional attack
- Influence maximization in complex networks through optimal percolation
- Mitigation of Malicious Attacks on Networks
- Small vulnerable sets determine large network cascades in power grids
- An Improved Discrete Bat Algorithm for Symmetric and Asymmetric Traveling Salesman Problems
- Network dismantling
- Optimization of Network Robustness to Waves of Targeted and Random Attack
- Two-Peak and Three-Peak Optimal Complex Networks
- A Discrete Firefly Algorithm to Solve a Rich Vehicle Routing Problem Modelling a Newspaper Distribution System with Recycling Policy
- Predicting percolation thresholds in networks
- A High Robustness and Low Cost Model for Cascading Failures
- Chaos in Small-World Networks
- Vulnerability and co-susceptibility determine the size of network cascades
- Optimal Percolation of Disordered Segregated Composites
- Variational Community Partition with Novel Network Structure Centrality Prior