Network Controllability is concerned about the structural controllability of 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 has recently been the subject of intense study by a number of groups, worldwide.
Consider the canonical linear time-invariant dynamics on a complex network where the vector captures the state of a system of nodes at time . The matrix describes the system's wiring diagram and the interaction strength between the components. The matrix identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector that the controller imposes on the system. To identify the minimum number of driver nodes, denoted by , whose control is sufficient to fully control the system's dynamics, Liu et al. attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed 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. They tried to develop an analytical framework, based on the in-out degree distribution, which predicts for scale-free and Erdős–Rényi Graphs. It is however notable, that their formulation would predict same values of 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, 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 and calculated by Liu et al. is notable. It is obvious that if controllability is decided mainly by degree, why are and so different for many real world networks? They argued  (arXiv:1203.5161v1), that this might be due to the effect of degree correlations. However, it has been shown that network controllability can be altered only by using betweenness centrality and closeness centrality, without using degree (graph theory) or degree correlations at all.
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.
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.
By calculating the maximum matchings of a wide range of real networks, Liu et al. 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. would predict same values of . Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of and calculated by Liu et al. is notable. If controllability is decided purely by degree, why are and so different for many real world networks? It remains open to scrutiny whether control robustness" in networks is influenced more by using betweenness centrality and closeness centrality over degree (graph theory) based metrics.
While sparser graphs are more difficult to control, it would obviously be interesting to find whether betweenness centrality and closeness centrality or degree heterogeneity plays a more important role in deciding controllability of sparse graphs with almost similar degree distributions.
- Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási, Nature 473 (2011).
- SJ Banerjee and S Roy, ARXIV:1209.3737
- C.-T. Lin, IEEE Trans. Auto. Contr. 19 (1974).
- R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr. 21 (1976).
- K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr. 21 (1976).
- L. Zdeborova and M. Mezard, J. Stat. Mech. 05 (2006).