Yangliu61

Controlling a simple network.

Controllability concerns our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control.

The controllability of general directed and weighted complex networks was systematically studied by Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László Barabási. Their work was published in the May 2011 issue of Nature in the article "Controllability of Complex Networks,".

Background

Consider the canonical linear time-invariant dynamics on a complex network

${\dot {\mathbf {X} }}(t)=\mathbf {A} \cdot \mathbf {X} (t)+\mathbf {B} \cdot \mathbf {u} (t)$

where the vector $\mathbf {X} (t)=(x_{1}(t),\cdots ,x_{N}(t))^{\mathrm {T} }$ captures the state of a system of $N$ nodes at time $t$. For example, $x_{i}(t)$ can denote the amount of traffic that passes through a node $i$ on a communication network, or transcription factor concentration in a gene regulatory network. The $N\times N$ matrix $\mathbf {A}$ describes the system's wiring digram and the interaction strength between the components, like the traffic on individual communication links or the strength of a regulatory interaction. Finally, $\mathbf {B}$ is the $N\times M$ input matrix $(M\leq N)$ that identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector $\mathbf {u} (t)=(u_{1}(t),\cdots ,u_{M}(t))^{\mathrm {T} }$ that the controller imposes on the system. In general, the same signal $u_{i}(t)$ can drive multiple nodes. If we wish to control a system, we first need to identify the set of nodes that, if driven by different signals, can offer full control over the network. These nodes are called driver nodes . We are particularly interested in identifying the minimum number of driver nodes, denoted by $N_{\mathrm {D} }$, whose control is sufficient to fully control the system's dynamics. The small network shown in the figure can be controlled by an input vector $\mathbf {u} =(u_{1}(t),u_{2}(t))^{\mathrm {T} }$ (left panel), allowing us to move it from its initial state to any desired final state in its state space (right panel). Given the state matrix $\mathbf {A}$ and the input matrix $\mathbf {B}$ of the network, the controllability matrix $\mathbf {C} ={\begin{bmatrix}\mathbf {B} &\mathbf {AB} &\mathbf {A^{2}B} \end{bmatrix}}$ can be shown to have full rank, indicating that the system is completely controllable by controlling nodes $x_{1}$ and $x_{2}$ using different signals $u_{1}(t)$ and $u_{2}(t)$. $x_{1}$ and $x_{2}$ are therefore the driver nodes of the network.

To check Kalman’s controllability rank conditionon, i.e. ${\text{rank}}\,\mathbf {C} ={\text{rank}}\,{\begin{bmatrix}\mathbf {B} &\mathbf {AB} &\mathbf {A^{2}B} &...&\mathbf {A^{N-1}B} \end{bmatrix}}=N$, for an arbitrary network, we need to know the weight of each link (i.e. the elements of $\mathbf {A}$), which for most real networks are either unknown (for example regulatory networks) or are known only approximately and are time dependent (for example Internet traffic). Even if all weights are known, a brute-force search requires us to compute the rank of $\mathbf {A}$ for $2^{N}-1$ distinct combinations, which is a computationally prohibitive task for large networks. To bypass the need to measure the link weights, we note that the system ($\mathbf {A,B}$) is ‘structurally controllable’ if it is possible to choose the non-zero weights in $\mathbf {A}$ and $\mathbf {B}$ such that its controllability matrix has full rank. A structurally controllable system can be shown to be controllable for almost all weight combinations, except for some pathological cases with zero measure that occur when the system parameters satisfy certain accidental constraints. Thus, structural controllability helps us to overcome our inherently incomplete knowledge of the link weights in $\mathbf {A}$. To avoid the brute-force search for driver nodes, Liu et al. proved that the minimum number of inputs or driver nodes needed to maintain full control of the network is determined by the 'maximum matching’ in the network, that is, the maximum set of links that do not share start or end nodes.

A schematic digram shows the control of a directed network. For a given directed network (Fig. a), we calculate its maximum matching: a largest set of edges without common heads or tails. It can be shown that the maximum matching will be composed 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 we need to control, i.e. the driver nodes. By injecting signals to those driver nodes, we get 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", we get "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem, 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.

Structutral Controllability

The concept of the structural properties was first introduced by Lin (1974) and then extended by Shields and Pearson (1976) and alternatively derived by Glover and Silverman (1976). The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.

Maximum Matching

In graph theory, a matching is a set of edges without common vertices. Liu et al. extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical Hopcroft–Karp algorithm, which runs in O(E√N) time in the worst case.

For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the cavity method developed in statistical physics. Liu et al. extended the calculations for directed graph.

Main results

By calculating the maximum matchings of a wide range of real networks, rather surprisingly, Liu et al. found that the number of driver nodes is determined mainly by the networks degree distribution $P(k_{\mathrm {in} };k_{\mathrm {out} })$. This prompted them to analytically calculate the average number of driver nodes for a network ensemble with arbitrary degree distribution using the cavity method.

Using a combination of analytical and numerical tools, they showed that controllability is determined by two network characteristics: average degree and degree heterogeneity. They also showed that controllability is rather robust to link failures and mapped the control robustness problem into core percolation, and thus calculated its dependence on network parameters.

By applying these tools to a wide range of real networks, they arrived to the unexpected conclusion that sparse and degree heterogeneous networks are the most difficult to control, which are exactly the characteristics that are found in many complex systems, from the cell to the Internet. They also showed that in most real systems most links can be removed without affecting our ability to control the whole system.

Future work

The framework presented in Ref. raises a number of questions, answers to which could further deepen our understanding of control in complex environments. For example, although the analytical work focused on uncorrelated networks, the algorithmic method developed there can identify N_D for arbitrary networks, providing a framework in which to address the role of correlations systematically.

The ability of a single node in controlling a directed weighted network is also interesting. To understand which topological characteristics determine a single node's ability from the control perspective is a non-trivial task. The result may help us design an effective attack strategy against the controllability of malicious networks, without requiring the detailed knowledge of the network structure.