Network controllability

Consider the canonical linear time-invariant dynamics on a complex network ${\displaystyle {\dot {\mathbf {X} }}(t)=\mathbf {A} \cdot \mathbf {X} (t)+\mathbf {B} \cdot \mathbf {u} (t)}$ where the vector ${\displaystyle \mathbf {X} (t)=(x_{1}(t),\cdots ,x_{N}(t))^{\mathrm {T} }}$ captures the state of a system of ${\displaystyle N}$ nodes at time ${\displaystyle t}$. The ${\displaystyle N\times N}$ matrix ${\displaystyle \mathbf {A} }$ describes the system's wiring diagram and the interaction strength between the components. The ${\displaystyle N\times M}$ matrix ${\displaystyle \mathbf {B} }$ identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector ${\displaystyle \mathbf {u} (t)=(u_{1}(t),\cdots ,u_{M}(t))^{\mathrm {T} }}$ that the controller imposes on the system. To identify the minimum number of driver nodes, denoted by ${\displaystyle N_{\mathrm {D} }}$, whose control is sufficient to fully control the system's dynamics, Liu et al.[2] attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed[2] that the minimum number of inputs or driver nodes needed to maintain full control of the network is determined by the maximum-cardinality matching in the network. From this result, an analytical framework, based on the in–out degree distribution, was developed to predict ${\displaystyle n_{\mathrm {D} }=N_{\mathrm {D} }/N}$ for scale-free and Erdős–Rényi random graphs.[2] However, more recently it has been demonstrated that network controllability (and other structure-only methods that use exclusively the connectivity of a graph, ${\displaystyle \mathbf {A} }$, to simplify the underlying dynamics), both undershoot and overshoot the number and which sets of driver nodes best control network dynamics, highlighting the importance of redundancy (e.g. canalization) and non-linear dynamics in determining control.[3]

It is also notable that Liu's et al. formulation[2] would predict same values of ${\displaystyle {n_{\mathrm {D} }}}$ for a chain graph and for a weak densely connected graph. Obviously, both these graphs have very different in and out degree distributions. A recent unpublished work[4] questions whether degree, which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of ${\displaystyle {n_{\mathrm {D} }}^{real}}$ and ${\displaystyle {n_{\mathrm {D} }}^{\mathrm {rand\_degree} }}$ calculated by Liu et al.[2] is notable. If controllability is decided mainly by degree, why are ${\displaystyle {n_{\mathrm {D} }}^{real}}$ and ${\displaystyle {n_{\mathrm {D} }}^{\mathrm {rand\_degree} }}$ so different for many real world networks? They argued[2] (arXiv:1203.5161v1) that this might be due to the effect of degree correlations. However, it has been shown[4] that network controllability can be altered only by using betweenness centrality and closeness centrality, without using degree (graph theory) or degree correlations at all.

A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem,[5] since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.

A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively.[9] This framework permits formulation of Kalman's criterion with tools from algebraic graph theory via the minimum rank of a graph and related notions.[10][11]

• Controllability Gramian

• The network controllability project website
• The video showing network controllability