Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
arXiv:1409.7831 · doi:10.1038/srep08321
Abstract
We study the vulnerability of dominating sets against random and targeted node removals in complex networks. While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed. We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost. We develop two new methods for finding flexible dominating sets, allowing either adjustable overall resilience, or dominating set size, while maximizing the dominated fraction of the remaining network after the attack. We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.
References in corpus (21)
- Error and attack tolerance of complex networks
- Assortative mixing in networks
- Mixing patterns in networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Attack vulnerability of complex networks
- Breakdown of the Internet under intentional attack
- Generating simple random graphs with prescribed degree distribution
- Stability and topology of scale-free networks under attack and defense strategies
- Emergence of bimodality in controlling complex networks
- Optimization of Robustness of Complex Networks
- Optimization of Network Robustness to Waves of Targeted and Random Attack
- Uncovering disassortativity in large scale-free networks
- Degree-degree correlations in random graphs with heavy-tailed degrees
- Minimum Dominating Sets in Scale-Free Network Ensembles
- Network Observability Transitions
- Distance-d covering problems in scale-free networks with degree correlations
- Cascading failures in spatially-embedded random networks
- MIGRAINE: MRI Graph Reliability Analysis and Inference for Connectomics
- Structurally Robust Control of Complex Networks
- Dominating Scale-Free Networks Using Generalized Probabilistic Methods