Network controllability

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.

The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide.

Recent studies by Sharma et al.[1] on multi-type biological networks (gene–gene, miRNA–gene, and protein–protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.

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

describes the system's wiring diagram and the interaction strength between the components.

The system is controlled through the time dependent input vector

To identify the minimum number of driver nodes, denoted by

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

[2] However, more recently it has been demonstrated that network controllability (and other structure-only methods that use exclusively the connectivity of a graph,

[3] It is also notable that Liu's et al. formulation[2] would predict same values of

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.

The concept of the structural properties was first introduced by Lin (1974)[5] and then extended by Shields and Pearson (1976)[6] and alternatively derived by Glover and Silverman (1976).

[7] 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.

In graph theory, a matching is a set of edges without common vertices.

Liu et al.[2] 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.

[8] Liu et al.[2] extended the calculations for directed graph.

By calculating the maximum matchings of a wide range of real networks, Liu et al.[2] asserted that the number of driver nodes is determined mainly by the networks degree distribution

They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the cavity method.

It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al.[2] would predict same values of

While sparser graphs are more difficult to control,[2][4] it would obviously be interesting to find whether betweenness centrality and closeness centrality[4] or degree heterogeneity[2] plays a more important role in deciding controllability of sparse graphs with almost-similar degree distributions.

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.

Controlling a simple network.
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.