July 13, 2011

"Q: Is Control controlled by its need to control? A: Yes."

Attention conservation notice: 1800+ words on yet more academic controversy over networks. (Why should those of us in causal inference have all the fun?) Contains equations, a plug for the work of a friend, and an unsatisfying, "it's more complicated than that" conclusion. Wouldn't you really rather listen to William Burroughs reading "Ah Pook Is Here"?

The following paper appeared a few months ago:

Yang-Yu Liu, Jean-Jacques Slotine and Albert-László Barabási, "Controllability of complex networks", Nature 473 (2011): 167--173 [PDF reprint courtesy of Prof. Barabási; the supplemental files, which contain all the actual math, are available from his publications page]
Abstract: The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered and natural systems towards a desired state, a framework to control complex self-organized systems is lacking. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes with time-dependent control that can guide the system's entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the network's degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but that dense and homogeneous networks can be controlled using a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the high-degree nodes.

(I will hold my tongue over the philosophy of science in the first sentence of the abstract.)

Liu et al. looked specifically at systems of linear differential equations, with one (scalar) variable per node, and some number of outside control signals. Numbering the nodes/variables from 1 to \( N \), the equation for the \( i^{\mathrm{th}} \) node is \[ \frac{dx_i(t)}{dt} = \sum_{k=1}^{N}{a_{ik}x_k(t)} + \sum_{j=1}^{P}{b_{ij}u_j(t)} \] Here the x variables are the internal variables of the system, and the u variables are the control signals. The coefficients \( a_{ik} \) encode the connections between nodes of the assemblage; non-zero coefficients indicate links in the network. The \( b_{ij} \) coefficients represent coupling of the network nodes to the input signals. If you can't, or won't, read the equation, an adequate English translation is "the change in the state of each node depends on the state of its neighbors in the network, and the outside inputs the node receives".

Following the engineers, we say that the system is controllable if it can be moved from any state vector \( x \) to any other state vector \( x^{\prime} \), in a finite time, by applying the proper input signal \( u(t) \). (This abstracts from questions about deciding what state to put it in, or for that matter about how we know what state it starts in ["observability"].) Liu et al. asked how the graph --- the pattern of non-zero links between nodes --- affects controllability. It's easy to see that it has to matter some: to give a trivial example, imagine that the nodes form a simple feed-forward chain, \( x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{N-1} \rightarrow x_N \), only the last of which gets input. This system cannot then be controlled, because there is no way for an input at the last node to alter the state at any earlier one. Liu et al. went through a very ingenious graph-theoretic argument to try to calculate how many distinct inputs such linear networks need, in order to be controlled.

Their conclusions are telegraphed in their abstract, which however does not play up one of their claims very much: namely, the minimum number of inputs needed is usually, they say, very large,, a substantial fraction of the number of nodes in the network. This is, needless to say, bad news for anyone who actually has a dynamical system on a complex network which they want to control.

Before we start making too much of this (I can already imagine the mangled David Brooks rendition, if it hasn't appeared already), it's worth pointing out a slight problem: the Liu et al. result is irrelevant to any real-world network.

Noah J. Cowan, Erick J. Chastain, Daril A. Vilhena, James S. Freudenberg, Carl T. Bergstrom, "Controllability of Real Networks", arxiv:1106.2573
Abstract Liu et al. have forged new links between control theory and network dynamics by focusing on the structural controllability of networks (Lui et al., Nature:473(7346), 167-173, 2011). Two main results in the paper are that (1) the number of driver nodes, ND, necessary to control a network is determined by the network's degree distribution and (2) ND tends to represent a substantial fraction of the nodes in inhomogeneous networks such as the real-world examples considered therein. These conclusions hinge on a critical modeling assumption: the dynamical system at each node in the network is degenerate in the sense that it has an infinite time constant, implying that its value neither grows nor decays absent influence from inbound connections. However, the real networks considered in the paper---including food webs, power grids, electronic circuits, metabolic networks, and neuronal networks---manifest dynamics at each node that have finite time constants. Here we apply Liu et al.'s theoretical framework in the context of nondegenerate nodal dynamics and show that a single time-dependent input is all that is ever needed for structural controllability, irrespective of network topology. Thus for many if not all naturally occurring network systems, structural controllability does not depend on degree distribution and can always be conferred with a single independent control input.
(Disclaimer: Carl is a friend, and I've often plugged his work over the years [1, 2, 3, 4]. However, the opinions in this post are mine, not his.)

Look at the equation for the Liu et al. model: \( x_i \), the state of the node in question, does not appear on the right-hand side. This means that, in their model, nodes have no internal dynamics --- they change only due to outside forces, otherwise they stay put wherever they happen to be. A more typical linear model, which does allow for internal dynamics, would be \[ \frac{dx_i(t)}{dt} = -p_i x_i(t) + \sum_{k=1}^{N}{a_{ik}x_k(t)} + \sum_{j=1}^{P}{b_{ij}u_j(t)} \] In words, "the change in the state of each node depends on its present state, the state of its neighbors in the network, and the outside inputs the node receives". This is of course a far more typical situation than the current state of a node being irrelevant to how it will change.

This seems like a very small change, but it has profound consequences for these matters. As Cowan et al. say, one can actually bring this case within the mathematical framework of Liu et al. by treating the internal dynamics of each node as a loop from the node to itself. Doing so has the immediate consequence (Proposition 1 in Cowan et al.) that any directed network could be controlled with only one input signal. To give a very rough analogy, in the Liu et al. model, a node move only as long as it is being actively pushed on; as soon as the outside force is released, it stops. In the more general situation, nodes can and will move even without outside forcing --- since it's a linear model, the natural motions are combinations of sinusoidal oscillations and exponential return to equilibrium --- and this actually makes it easier to drive the system to a desired state. It is a little surprising that this always reduces the number of input signals needed to 1, but that does indeed follow very directly from Liu et al.'s theorems.

Now, constant readers may have been wondering about why I've not said anything about the linearity assumption. Despite appearances, I actually have nothing against linear models --- some of my best friends use nothing but linear models --- and it seemed perfectly reasonable to me that Liu et al. would work with a linear set-up, at least as a local approximation to the real nonlinear dynamics. Unfortunately, that turns out to be a really bad way to approximate this sort of qualitative property:

Wen-Xu Wang, Ying-Cheng Lai, Jie Ren, Baowen Li, Celso Grebogi, "Controllability of Complex Networks with Nonlinear Dynamics",arxiv:1107.2177
Abstract: The controllability of large linear network systems has been addressed recently [Liu et al. Nature (London), 473, 167 (2011)]. We investigate the controllability of complex-network systems with nonlinear dynamics by introducing and exploiting the concept of "local effective network" (LEN). We find that the minimum number of driver nodes to achieve full control of the system is determined by the structural properties of the LENs. Strikingly, nonlinear dynamics can significantly enhance the network controllability as compared with linear dynamics. Interestingly, for one-dimensional nonlinear nodal dynamics, any bidirectional network system can be fully controlled by a single driver node, regardless of the network topology. Our results imply that real-world networks may be more controllable than predicted for linear network systems, due to the ubiquity of nonlinear dynamics in nature.
The local effective network works just like you'd imagine: basically, take the nonlinear dynamics, linearize them by a Taylor series around your favorite operating point, and treat the non-zero-to-first-order couplings as edges. After that point, everything goes very much as in the Cowan et al. paper, which, oddly, is not cited. (Wang et al.'s language, drawn from nonlinear dynamics, is much more homely and familiar to me than is Cowan et al.'s, which comes from control systems, but under the words the stories are the same.)

As Cowan et al. go on to observe, being controllable is an entirely qualitative property --- it says "there exists a control signal", not "there exists a control signal you could ever hope to apply". There are several ways of quantifying how hard it is to control a technically-controllable system, and this seems unavoidably to depend on much more information than just that provided by the network's degree distribution, or even the full graph of the network. This would be particularly true of nonlinear systems, which of course are most of the interesting ones.

So, to sum up, there were two very striking and interesting claims in the Liu et al. paper: (i) that the degree distribution alone of a network gives us deep insight into its a specific aspect of its dynamics, and (ii) this shows that most complex networks are very hard to control. What both the follow-up papers show is that (ii) is wrong, that with this sense of "control", you can, generically, control an arbitrarily complex network by manipulating just a single input signal. But this, together with the recognition that we need to get beyond this very qualitative notion of control, also undermines (i). That to me is rather disappointing. It would have been great if we could have inferred so much from just the degree distribution. (It would have given us a good reason to care about the degree distribution!) Instead we're back to the messy situation where ignoring the network leads us into error, but merely knowing the network doesn't tell us enough to be useful, and non-network details matter. Back, I suppose, to the science.

Aside I may regret later: Barabási really does not have a great track record when it comes to Nature cover-stories, does he? But, if past trends hold good, neither the Cowan et al. nor the Wang et al. paper have any chance of appearing in that journal.

Manual trackback: Resilience Science

Update, 29 July 2011: I should have been clearer above that the paper by Wang et al. is not written as a comment on the original Nature paper, unlike that by Cowan et al.

Update, 30 August 2011: I haven't had a chance to read it, but I thought it only right to note the appearance of "Comment on 'Controllability of Complex Networks with Nonlinear Dynamics'," by Jie Sun, Sean P. Cornelius, William L. Kath, and Adilson E. Motter (arxiv:1108.5739).

Networks; Complexity; Mathematics

Posted at July 13, 2011 19:35 | permanent link

Three-Toed Sloth