Profiting from Nonlinearity and Interconnectivity to Control Networks
Authors: Sean P. Cornelius1 & Adilson E. Motter1,2
1Department of Physics & Astronomy, Northwestern University, USA.
2Northwestern Institute on Complex Systems, Northwestern University, USA.
The concept of a complex network---a set of “nodes'” connected by “links” that represent interactions between them---pervades science and engineering, describing systems as diverse as food webs, power grids, and cellular metabolism . Due to the interconnected nature of such systems, perturbations that affect one or more nodes can propagate through the network and potentially cause the system as a whole to fail or change behavior. But our study, recently published in Nature Communications , shows that this principle can be a blessing in disguise, giving rise to a new strategy to control network behavior.
A hallmark of real complex networks, both natural and engineered, is that their dynamics are inherently nonlinear . It is this nonlinearity that permits the coexistence of multiple stable states (some desirable, others not), which correspond to different possible modes of operation of a real network. Because of this, when a network is perturbed, it can spontaneously go to a “bad” state even if there are “good” ones available. The question we asked is: can this principle be applied in reverse? In other words, can we perturb a network that is in (or will approach) a “bad” state in such a way that it spontaneously evolves to a target state with more desirable properties?
Our research was motivated by recent case studies in our research group, which showed how networks damaged by an external perturbation can, counter-intuitively, be healed by intentionally applying additional, compensatory perturbations. For example, bacterial strains left unable to grow in the wake of genetic mutations can be made viable again by the further knockout of specific genes , while extinction cascades in ecological networks perturbed by the loss of one species can often be mitigated by the targeted suppression of additional species . However, a systematic extension of such a strategy to general networks remained an open problem, partly due to system-specific constraints that restrict the perturbations one can actually implement. Indeed, in most real networks there are constraints on the potential compensatory perturbations one can implement in the system, and these generally preclude bringing the system directly to the target, or even to a similar state. In food-web networks, for instance, it may only be possible to suppress (but not increase) the populations of certain species (e.g., via hunting, fishing, culling, or non-lethal removals), while some endangered species can't be manipulated at all. Similarly, one can easily knock down one or more genes in a genetic network, but coordinating the upregulation of entire genetic pathways is comparatively difficult.
The critical insight underlying our research is that even when a desired stable state of a dynamical system can't be reached directly, there will exist a set of other states that eventually do evolve to the target---the so-called basin of attraction of that state. If we could only bring the system to one of those states through an eligible perturbation, the system would subsequently reach the target on its own, without any further intervention. A core component of our work is thus the introduction of a scalable algorithm that can locate basins of attraction in a general dynamical system  (for a Python implementation of the algorithm, see Ref. ). Figure 1 presents a visual illustration of this approach for transitions between patterns stored in an associative memory network, in which the control intervention (downward arrows) causes the network to spontaneously transition to the next pattern under time evolution (diagonal arrows).
Figure 1: Patters representing the letters of the word “NETWORK” are stored as different stable states in an associative memory network. The example shows how our algorithm induces transitions between consecutive letters by only perturbing “off” pixels.
A remarkable aspect of this approach is its robustness. In the example just mentioned, the control procedure succeeds in driving the system to the target or to a similar pattern with a small number of binary errors (gray pixels). Thus, even if the target state cannot be reached by any eligible perturbation, it may nonetheless be possible to drive the network to a similar state using this control procedure. This would not be possible if the dynamics were linear, since in that case the nonlocal nature of the control trajectories may prevent numerical convergence to the desired target even when the initial state is already close to the target .
The approach is based on casting the problem as a series of constrained nonlinear optimization problems, which enables systematic construction of compensatory perturbations via small imaginary changes to the state of the network. Prior to the introduction of this technique there were no systematic methods for locating the portions in the attraction basins that can be reached by eligible perturbations in general high-dimensional dynamical systems, short of conservative estimates and brute-force sampling. The latter requires an amount of computation time exponential in the number of dynamical variables of the system, which is notoriously large for complex networks of interest. In contrast, the running time of our approach scales only as the number of variables to the power 2.5.
There are numerous potential applications for the above control approach. As an example, we considered the identification of candidate therapeutic targets in a form of human blood cancer caused by the abnormal survival of cytotoxic T-cells. Here, normal and cancer states correspond to two different types of stable steady states . Potential curative interventions are those that bring the system from a cancerous or pre-cancerous network state to the attraction basin of the normal state, which then leads to programmed cell death. We demonstrate that 2/3 of all such compromised states can be rescued through perturbations limited to network nodes not previously identified as promising candidate targets for therapeutic interventions. Furthermore, we show that perturbing an average of only 3.4 of them suffices to control the entire network. The effectiveness of many approved drugs relies on their being multi-target, temporary, and tunable, which are precisely the characteristics of the type of control interventions introduced by our study, making such predictions attractive for future experimental exploration .
This work illustrates how interconnectedness and nonlinearity---unavoidable features of real systems commonly thought to be impediments to their control---can actually be turned to our advantage. This has broad implications and may in particular shed new light on the requirements on the observability of real networks to allow their real-time control (for recent studies on network observability, see Refs. [10, 11]).
Our approach is based on the systematic construction of compensatory perturbations to the network, and, as illustrated in our applications, can account for both rather general constraints on the admissible interventions and the nonlinear dynamics inherent to most real complex networks. These results provide a new foundation for the control and rescue of network dynamics and for the related problems of cascade control, network reprogramming, and transient stability. In particular, we expect these results to have implications for the development of smart traffic and power-grid networks, of new ecosystem and Internet management strategies, and of new interventions to control the fate of living cells.
The research was supported by NSF (Grant DMS-1057128), NCI (Grant 1U54CA143869), and a Northwestern-Argonne Early Career Investigator Award.
 Mark Newman, "The physics of networks", Physics Today, 61(11), 33 (2008). Full Article.
 Sean P. Cornelius, William L. Kath, Adilson E. Motter, "Realistic control of network dynamics", Nature Communications, 4, 1942 (2013). Abstract.
 Adilson E. Motter and Réka Albert, "Networks in motion", Physics Today 65(4), 43 (2012). Full Article.
 Adilson E Motter, Natali Gulbahce, Eivind Almaas & Albert-László Barabási, "Predicting synthetic rescues in metabolic networks", Molecular Systems Biology, 4, 168 (2008). Full Article.
 Sagar Sahasrabudhe & Adilson E. Motter, "Rescuing ecosystems from extinction cascades through compensatory perturbations", Nature Communications, 2, 170 (2011). Abstract.
 Sean P. Cornelius & Adilson E. Motter, "NECO - A scalable algorithm for NEtwork COntrol", Protocol Exchange, Nature Protocols (2013), doi:10.1038/protex.2013.063. Link.
 Jie Sun and Adilson E. Motter, "Controllability transition and nonlocality in network control", Physical Review Letters, 110, 208701 (2013). Abstract.
 Ranran Zhang, Mithun Vinod Shah, Jun Yang, Susan B. Nyland, Xin Liu, Jong K. Yun, Réka Albert, Thomas P. Loughran, Jr. "Network model of survival signaling in large granular lymphocyte leukemia". Proceedings of the National Academy of Sciences of the United States of America, 105, 16308 (2008). Abstract.
 Peter Csermely, Tamás Korcsmáros, Huba J.M. Kiss, Gábor London, Ruth Nussinov, "Structure and dynamics of molecular networks: A novel paradigm of drug discovery", Pharmacology & Therapeutics, 138, 333 (2013). Abstract.
 Yang Yang, Jianhui Wang, and Adilson E. Motter, "Network observability transitions", Physical Review Letters, 109, 258701 (2012). Abstract.
 Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László Barabási, "Observability of complex systems", Proceedings of the National Academy of Sciences of the United States of America, 110, 2460 (2013). Abstract.