Security-Aware Network Analysis for Network Controllability

Shuo Zhang, Stephen Wolthusen

Research output: Contribution to conferencePaperpeer-review

79 Downloads (Pure)


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.
Original languageEnglish
Number of pages7
Publication statusPublished - 2018
EventAINA-2018 Workshops: The 5th International Workshop on Security Intricacies in Cyber-Physical Systems and Services (INTRICATE-SEC-2018) - Kracow, Poland
Duration: 16 May 201818 May 2018


WorkshopAINA-2018 Workshops


  • Network Analysis
  • Edge Classification
  • Network Controllability
  • Maximum Matching

Cite this