Critical node analysis (CNA) of electrical infrastructure networks

This work addresses the problem of identifying the set of nodes in a power network critical to system operation. Formally, the CNA problem is the problem of identifying a minimum cardinality set of nodes to target in a power network in order to reduce throughput by a given factor. Since the defender may reroute flows in an attempt to restore throughput, the attack must anticipate and defeat this possibility. We develop here an algorithm to solve this problem. In our approach we model the problem as a bi-level optimization problem where the master problem attempts different attack combinations and the sub-problem responds with the best routing. The optimization problems that result from such a framework are mixed integer programs (MIPs), which we solve in our implementation using IBM CPLEX. The algorithm has been tested on several benchmark networks and appears to perform well. We have also developed variants that can be used for determining optimal restoration configuration post damage on large networks (4000 nodes, 8000 links) and for modeling propagation of failures after the initial attack. We report on computational experiments with these variants as well.