Recovering Structural Controllability on Erdös-Rényi Graphs via Partial Control Structure Re-Use

Bader Alwasel, Stephen D. Wolthusen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Controllability, or informally the ability to force a system
into a desired state in a finite time or number of steps, is a fundamental
problem studied extensively in control systems theory with structural
controllability recently gaining renewed interest. In distributed control
systems, possible control relations are limited by the underlying network
(graph) transmitting the control signals from a single controller or set of
controllers. Attackers may seek to disrupt these relations or compromise
intermediate nodes, thereby gaining partial or total control.
For a defender to re-gain full or partial control, it is therefore critical to
rapidly reconstruct the control graph as far as possible. Failing to achieve
this may allow the attacker to cause further disruptions, and may - as
in the case of electric power networks - also violate real-time constraints
leading to catastrophic loss of control. However, as this problem is known
to be computationally hard, approximations are required particularly
for larger graphs. We therefore propose a reconstruction algorithm for
(directed) control in Erdöos-Rényi random graphs to reduce the averagecase
complexity through partial re-use of PDS based on the formulation
of our recent work presented as an extended abstract
Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Critical Information Infrastructures Security (CRITIS 2014)
ISBN (Electronic)978-3-319-31664-2
ISBN (Print)978-3-319-31663-5
Publication statusPublished - 2014


  • Structural Controllability, Power Dominating Sets, Recovery from Attacks

Cite this