Building damage-resilient dominating sets in complex networks against random and targeted attacks

Area of Science:

• Network Science
• Graph Theory
• Cybersecurity

Background:

• Dominating sets are crucial for network controllability and observability.
• Existing research often assumes network integrity, overlooking vulnerability.
• Small, cost-efficient dominating sets are particularly susceptible to node loss.

Purpose of the Study:

• To investigate the vulnerability of dominating sets in complex networks under node removal.
• To develop novel methods for constructing resilient dominating sets.
• To enhance network controllability and observability post-attack.

Main Methods:

• Analysis of dominating set vulnerability against random and targeted node removals.
• Development of two new algorithms for flexible dominating set construction.
• Evaluation of methods on synthetic scale-free and real-world complex networks.

Main Results:

• Cost-efficient dominating sets optimized for size are highly vulnerable to damage.
• A small fraction of dominator node loss can severely disrupt network domination.
• The proposed methods effectively create dominating sets with adjustable resilience or size.

Conclusions:

• Network robustness requires considering dominating set resilience, not just size.
• Flexible dominating sets offer improved network control and observability after damage.
• The developed methods provide practical solutions for securing complex networks.