Bounds for damage overlap in critical node attacks on networks
Objective Transfer in Single-Node Network Criticality: Optimal Constants and Exact Separation Thresholds
Discrete Mathematics
Summary
When trying to find the single most damaging point to attack in a network, different ways of measuring damage can lead to different targets. The authors studied how well a target chosen to maximize damage under one measure also causes damage under another. They found exact limits on how much damage is retained for common damage measures and identified when the best targets for these measures differ. Their work relies on examining all small connected networks and shows the optimal constants hold for bigger networks too.
What this means in practice
- •For network security teams: Identify single critical nodes for network attacks accounting for different damage measures with guaranteed performance bounds.
- •For infrastructure resilience planners: Guide protection strategies by understanding when a single vulnerable point affects multiple aspects of network connectivity.
Tested on simulated data.
Authors
Onur Ugurlu
Abstract
When a vertex is selected as the most damaging single attack target under one damage objective, how much of the optimal damage under a different objective does it retain? We study this for the three objectives commonly used in critical node detection -- pairwise connectivity (PC), size of the largest surviving component (LCC) and number of components (NC) -- for single-vertex attacks on connected graphs, with the attacked vertex counted in the damage and ties resolved optimistically. For the pair PC, LCC the loss is bounded: a PC-optimal vertex retains at least a $2-\sqrt2$ fraction of the optimal LCC damage, an LCC-optimal vertex at least 2/3 of the optimal PC damage, and both constants are best possible. Neither bound depends on the choice among tied optimal vertices or on whether the attacked vertex is counted, and both remain valid as lower bounds for attack sets of any fixed size. For the four directions involving NC no positive constant exists; explicit families have ratios decaying like 1/k, and no single attack set retains a positive fraction of all three optima uniformly. We also determine the smallest orders at which the sets of optimal vertices become disjoint: 7 for LCC/NC, 8 for PC/NC, 9 for PC/LCC and 11 for all three pairwise, with trees realising the triple separation for every n>=11; these values rest on an exhaustive enumeration of the 11,989,762 connected graphs with 3<=n<=10. Finally, the most critical vertex in a Birnbaum-type sense may depend on the failure probability: a six-vertex graph, of smallest possible order, changes leader once, at $p^*=3-\sqrt5$. Adding universal vertices lifts the budget-one examples to every fixed budget, so over all connected graphs the same constants are optimal at every fixed budget; behaviour within restricted classes such as trees is left open.