Stability of Dominating Sets in Complex Networks against Random and Targeted Attacks

Minimum dominating sets (MDS) are involved in efficiently controlling and monitoring many social and technological networks. However, MDS influence over the entire network may be significantly reduced when some MDS nodes are disabled due to random breakdowns or targeted attacks against nodes in the network. We investigate the stability of domination in scale-free networks in such scenarios. We define stability as the fraction of nodes in the network that are still dominated after some nodes have been removed, either randomly, or by targeting the highest-degree nodes. We find that although the MDS is the most cost-efficient solution (requiring the least number of nodes) for reaching every node in an undamaged network, it is also very sensitive to damage. Further, we investigate alternative methods for finding dominating sets that are less efficient (more costly) than MDS but provide better stability. Finally we construct an algorithm based on greedy node selection that allows us to precisely control the balance between domination stability and cost, to achieve any desired stability at minimum cost, or the best possible stability at any given cost. Analysis of our method shows moderate improvement of domination cost efficiency against random breakdowns, but substantial improvements against targeted attacks.