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:
(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.
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:
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).
Posted at July 13, 2011 19:35 | permanent link