Security-Aware Network Analysis for Network Controllability

Although people use critical, redundant and ordinary categories to concisely distinguish the importance of edges in maintaining the controllability of networks in linear time-invariant (LTI) model, a specific network analysis is still uncertain to confirm edges of each category and guide further edge protection. Given a large, sparse, ErdHos-Renyi random digraph that is in LTI model and has a known maximum matching, as an input network. We address the problem of efficiently classifying its all edges into those categories. By the minimal input theorem, classifying an edge into one of those categories is modeled into analysing the number of maximum matchings having it, and is solved by finding maximally-matchable edges via a bipartite graph mapped by the input network. In the worst case, entire edge classification is executed in linear time except for precomputing a maximum matching of the input network.