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.

- 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,*N*, necessary to control a network is determined by the network's degree distribution and (2)_{D}*N*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._{D}

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.

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