In classical control theory, determining whether a system is controllable—meaning it can be steered from any initial state to any target state—relies on algebraic tests like the Kalman rank condition. However, for large-scale networked systems such as drone swarms, power grids, or gene regulatory networks, knowing the exact numerical values of every interaction parameter is practically impossible. Furthermore, these values often fluctuate over time.
To bypass this limitation, researchers use structural controllability. Instead of looking at exact parameter values, structural controllability analyzes the wiring diagram of the system represented as a directed graph. A system is structurally controllable if it is controllable for almost all possible choices of non-zero edge weights.
The power of this approach lies in a fundamental insight: controllability is primarily a function of information flow and network topology. To make a network controllable, the graph structure must satisfy two core intuitive requirements: accessibility (signals must be able to reach every node) and the absence of dilations (signals must not bottleneck and lose their independent degrees of freedom).
Ensuring Accessibility via Leaders and Actuators
The most intuitive prerequisite for controlling a network is that a control signal must physically reach every single node. In multi-agent systems, this is often framed around "leaders" (nodes directly injected with external control inputs) and "followers" (nodes that learn state information from their neighbors).
For a network with a single leader, ensuring control is straightforward. In On Controllability of Leader-Follower Dynamics over a Directed Graph, Jayakumar Subramanian et al. prove that basic graph connectivity—where every follower node is accessible via a directed path from the leader—is both a necessary and sufficient condition for structural controllability.
[External Input] ──> [Leader Node] ──> [Follower 1] ──> [Follower 2]
When a network scales and requires multiple leaders to distribute authority, ensuring accessibility becomes more complex. If you partition a network into separate subgraphs, any subgraph left without a leader becomes an isolated island, completely immune to external influence. To prevent this, Milad Kazemi et al. introduce the concept of "leader-follower connectivity" in Structural Controllability of a Consensus Network With Multiple Leaders. They demonstrate that for any arbitrary partition of the network, at least one leader must reside in each resulting subgraph to guarantee overall system control.
Similarly, in networks that lack strong internal connectivity, identifying where to place control inputs is critical. In Actuator Placement for Structural Controllability beyond Strong Connectivity and towards Robustness, Baiwei Guo et al. show that control inputs must be placed in every "source component"—clusters of nodes that have outgoing connections but no incoming connections from the rest of the network. Without direct actuation on these source components, their states can never be altered by external signals.
Eliminating Structural Bottlenecks and Dilations
While path accessibility ensures that control signals reach every node, it does not guarantee that the signals remain independent. If two distinct target nodes can only receive information through a single shared bottleneck node, their states will become linearly dependent. In graph theory, this structural bottleneck is known as a dilation.
To eliminate dilations, a network must possess enough independent paths to distribute control signals without losing degrees of freedom. In Minimum input selection for structural controllability, Alex Olshevsky reformulates the challenge of finding the minimum number of inputs as a combinatorial problem on directed graphs. By leveraging maximum bipartite matching algorithms, the author demonstrates how to map state nodes to unique control inputs, mathematically proving that a system is free of dilations when there are no contracting subsets of state nodes.
Uncontrollable (Dilation): Controllable (Matched Paths):
[Input] [Input 1] [Input 2]
│ │ │
▼ ▼ ▼
[Node A] [Node A] [Node B]
╱ ╲ │ │
▼ ▼ ▼ ▼
[Node B] [Node C] [Node C] [Node D]
This requirement for structural independence manifests across various specialized network domains:
- Spatial Formations: In Controllability of Formations over Time-varying Graphs, Xudong Chen et al. analyze agents moving in $n$-dimensional space. They show that to maintain the necessary degrees of freedom to reach any target formation, every maximal strongly connected component within the communication network must contain at least $n+2$ members.
- Biological Networks: In Controllability of Conjunctive Boolean Networks with Application to Gene Regulation, Zuguang Gao et al. study gene regulation. They establish that to steer a conjunctive Boolean network, control nodes must be strategically chosen to break every natural feedback loop in the system's dependency graph, rendering the network structure acyclic so that signals do not get trapped in internal cycles.
Controllability in Switched and Multi-Mode Networks
Many real-world systems do not rely on a single static graph; instead, they switch between different operational modes or communication topologies over time. A powerful property of these switched linear systems is that a system can become globally controllable through mode switching, even if none of its individual constituent modes are controllable on their own.
To analyze this, Xiaomeng Liu et al. introduce the concept of a "colored union graph" in Structural controllability of switched linear systems. By overlaying the graphs of all subsystems and color-coding the edges based on the mode they belong to, the authors prove that structural controllability depends on finding a specific number of "S-disjoint edges" across the modes, corresponding to the system's total state dimension.
Building on this framework, Yuan Zhang 0016 et al. resolve subtle theoretical gaps in multi-mode control in Generalized Cactus and Structural Controllability of Switched Linear Continuous-Time Systems. They introduce a graphical configuration called a generalized cactus—a collection of vertex-disjoint independent paths (stems) and loops (buds). The authors demonstrate that if a generalized cactus structure spans all state nodes across the colored union graph, the control signal can successfully inject energy into every dimension of the multi-mode state space over time.
This interplay emphasizes that structural controllability in switched systems is a joint property of graph topology and algebraic constraints. As shown in Structural minimum controllability problem for switched linear continuous-time systems by Sérgio Pequito et al., optimizing actuator placement in these environments requires a dual approach that pairs graph-theoretic connectivity with algebraic generic rank conditions.
Scaling and Designing Controllable Networks
Understanding structural conditions allows engineers to not only analyze existing networks but also design networks that are guaranteed to remain controllable as they grow.
In Growing controllable networks via whiskering and submodular optimization, Mathias Hudoba de Badyn et al. explore structured graph-growing processes. They highlight a technique called whiskering—adding a new node and attaching it to an existing node via a dedicated edge—and prove that this localized structural addition inherently preserves the network's underlying controllability properties.
Existing Controllable Network ──> [Node A] ──(New Edge)──> [New Whisker Node]
Furthermore, these structural principles can be generalized across seemingly unrelated network families. In Laplacian Dynamics on Cographs: Controllability Analysis through Joins and Unions, Shima Sadat Mousavi et al. demonstrate that the controllability properties of specialized network types, such as threshold or cluster graphs, are specific instances of a broader theory governing complement-reducible structures (cographs). This unification proves that control strategies developed for simple, recursive graph hierarchies can be reliably scaled to a much wider class of complex networks.
Key Foundational Work
Leader localization in multi-agent systems subject to failure: A graph-theoretic approach (2011) — contributed 1 concept elements to this direction.
State-Based Control of Fuzzy Discrete-Event Systems (2005) — contributed 1 concept elements to this direction.