Lin's theorem: minimum driver nodes via maximum matching in directed networks
Network Parameters
ẋ = Ax + Bu
n_D = N − |M*|
n_D/N → depends on ⟨k_in⟩
Driver nodes n_D = —
Fraction n_D/N = —
Max matching |M*| = —
Type: ER random
Lin (1974): a network is structurally controllable iff we can steer all nodes using the minimum driver set.
n_D = N − |M*| where M* is the maximum matching of the directed graph.
Key finding (Liu et al. 2011): sparse and dense networks both need more driver nodes than intermediate ones; the minimum occurs near ⟨k⟩≈2–3.
Driver nodes shown in red; matched nodes in green; unmatched (drivers) highlighted.