Network controllability

Controlling a simple network.

Network Controllability concerns the controllability a network. Controllability describes 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,"^[1].

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. The $N \times N$ matrix $\mathbf{A}$ describes the system's wiring digram and the interaction strength between the components. The $N \times M$ matrix $\mathbf{B}$ 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. To identify the minimum number of driver nodes, denoted by N_D, whose control is sufficient to fully control the system's dynamics, Liu et al.^[1] combined the tools from structural control theory, graph theory and statistical physics and developed an analytical framework. They 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. Analytical solutions of N_D are derived for network ensembles with prescribed degree distributions.

A schematic digram 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^[2], 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)^[2] and then extended by Shields and Pearson (1976)^[3] and alternatively derived by Glover and Silverman (1976)^[4]. 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.^[1] 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^[5]. Liu et al.^[1] 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.^[1] found that the number of driver nodes is determined mainly by the networks degree distribution P(k_in;k_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^[6], 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.^[1] 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.

References

1. ^ ^{a b c d e f} Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási, Nature 473 (2011).
2. ^ ^{a b} C.-T. Lin, IEEE Trans. Auto. Contr. 19 (1974).
3. ^ R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr. 21 (1976).
4. ^ K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr. 21 (1976).
5. ^ L. Zdeborova and M. Mezard, J. Stat. Mech. 05 (2006).
6. ^ M. Bauer and O. Golinelli, Eur. Phys. J. B. 24(2001).

External links

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